[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 47 KB, 640x600, theWholeuniverse.gif [View same] [iqdb] [saucenao] [google]
1546225 No.1546225 [Reply] [Original]

nt isprime(int num)
{
int test;
int index;
for(index =2 ; index <= sqrt(num); index++)
{

test = num%index;
if(test== 0)
{
return 0;//returns nothing if not a prime
}
}


return num;//returns prime


}


//This is too slow, think it can be improved?
aside from being better commented and neater

>> No.1546243
File: 94 KB, 1200x767, oh god where am I.jpg [View same] [iqdb] [saucenao] [google]
1546243

>>1546225
Oh fuck, I can't remember how, but there's a way to skip indexes that are themselves not prime. I forgot how to do it though.

Sorry.

Will bump for someone with more than rudimentary programming skills.

>> No.1546246

>>1546225
>//This is too slow, think it can be improved?
You think?

The first degree of improvement could be

if (!odd(num)) return 0;
for(index =3 ; index <= sqrt(num); index+=2)

>> No.1546272

It depends how efficient you want to get. Look up the various sieves depending on how large a number you want to test. But generally, you want to hard code into a table the first 100 to 1,000 prime numbers.

If n < your highest prime, just check against the table. If n > your highest prime, try dividing by each prime in your table. If you still haven't found a divisor, and n > your highest prime squared, move on to a sieve.

>> No.1546281

precompute the square and store it in a variable, because the squareroot will likely to be recomputed each step.
Then look if its dividable by two. If it is, skip it.
Look if its dividable by three.
Looks if its dividable by five (because for is dividable by two and we already checked two).

maybe you can implement this better?
Ow, and it is easier if you have a list of prime numbers. Then you can just check for each prime number from 0 to sqr(number).

>> No.1546285

use some Sieve of Eratosthenes algo , take all the prime <= sqrt (num) in a list , do the test only with the number in the list.

>> No.1546288

>>1546281
I don't think sqrt() will be recomputed each time.

>> No.1546292

>>1546272
This sounds most efficient indeed

>> No.1546295

>>1546288
That'll depend on the compiler.

>> No.1546300

>>1546288
Dunno either, but I'm pretty shure that you can use a changing variable in the for-loop, and therefor it must be recomputed each time.

>> No.1546308

>>1546281
fuck,you might be right about that, unless the compiler is very smart and knows the square won't be changing then it will recompute

>> No.1546322

>>1546288
It will be, unless your compiler is smart enough to recognize the sqrt function as a pure function (in which case it might or might not be optimized).

>> No.1546324

>>1546300
But compilers ain't dumb. They can see that num is not assigned to in the scope of the loop. I'd be surprised if any popular compiler recalculated the sqrt().

>> No.1546330

int isprime( int num )
{
if( num == 2 )
return 1;

for( int i = 2; i <= 9; i++ )
if( num % i == 0 )
return 0;

return 1;
}

>> No.1546335

>>1546324
But they can't see that calls to sqrt() can safely be optimized away, unless they have a hardcoded list of library functions that are safe to optimize away. Which they certainly might, but it equally certainly isn't a given.

>> No.1546360

You can use the fact that all primes greater than 3 are 1 or 5 mod 6.

Test 2 and 3 manually then go:

for(index = 5 ; index <= sqrt(num); index+=2)
{
test = num%index;
if(test== 0)
{
return 0;//returns nothing if not a prime
}
index+=4
test = num%index;
if(test== 0)
{
return 0;//returns nothing if not a prime
}
}

Also, might want to throw in a if(num==2) return 2; if(num==3) return 3; if((num^2)%6 != 1) return 0; at the beginning.

>> No.1546366

Store a list of primes as a linked list from the bottom up.

For each number, keep modding with the primes until you get a 0 or reach the sqrt of the number itself.

First case, move on; second case, add number to list of primes, move on.

>> No.1546371

have an array filled with prime numbers, i.e.
P(0) = 2
P(1) = 3
P(2) = 5
P(3) = 7
and so on

Loop through the array to check if the current number is prime. If the current array number is larger than the square root of the number, its prime. Then add that number to the array.

pseudo-ish code:

while(OP wants to keep checking numbers)
{
num++
for(index = 0;P(index) < sqrt(num);index++)
{
if( num%P(index) == 0)
{
exit for, skip the next bit of code (don't use a goto if you can avoid it)
}
add 1 to the length of P
P(max) = num
}
}

>> No.1546374

>>1546324
Yeah, compiler designers know people are dumb and lazy when it comes to optimizing run speed.

>> No.1546382

oh wow, a thread in which we might actually contribute to science?

>> No.1546387

>>1546335
well, someone compile it to asm and find out what it does.

>> No.1546388

>>1546366
Linked list is slow. Arrays are faster.

>> No.1546391

>>1546382
lol no.

>> No.1546393

>>1546387
It depends on your compiler, obviously.

>> No.1546395

>>1546382
Not really. It's mostly copypasta from programming textbooks.

>> No.1546398

>>1546371

woops the adding to the array length should be be below another brace, but you get the idea

>> No.1546401

use an sqrt approximation

>> No.1546400

>>1546388
arrays don't grow. Might as well use a hash table.

>> No.1546403

>>1546400
Hash tables are even slower. Arrays can "grow" in a sense that you can move on to another array once the previous one fills up. You just have to keep track of how much of the array you've used up.

>> No.1546411

>>1546400
Dynamically allocated arrays don't exist? I never knew.

>> No.1546421

>>1546411
They exist, but they don't grow.

>> No.1546424

>>1546388

Arrays don't expand dynamically. Individual chains ensure that the links stay on the stack when you get shittons of numbers.

>> No.1546429

>>1546411
dynamically allocated arrays are fixed in size.

>> No.1546446

>>1546424
More numbers mean more memory is required if you're using linked lists. They're meant to be used for objects, not something as trivial as integers. With some creative thinking you can use a set of arrays to hold the prime numbers.

>> No.1546453

>>1546446
>More numbers mean more memory is required if you're using linked lists.
I think you mean that less numbers mean less memory is required if you're using linked lists. No, that's not the same thing.

>They're meant to be used for objects, not something as trivial as integers.
They're meant to be used for everything.

>With some creative thinking you can use a set of arrays to hold the prime numbers.
Of course you can. It's just that a linked list is more efficient here.

>> No.1546456

>>1546446
>With some creative thinking you can use a set of arrays to hold the prime numbers.
I doubt it, considering the amount of primes is infinite.

>> No.1546460

>>1546456
Memory of computer isn't infinite. You're just using a strawman here.

>> No.1546474

>>1546460
Do you even know what a strawman is? Because this ain't it.

>> No.1546476

>>1546453
>Of course you can. It's just that a linked list is more efficient here.
How can a linked list be more efficient if you have to allocate memory at every iteration of the loop and it takes up more memory for each integer than an array?

>> No.1546493

>>1546474
While it's correct that there are an infinite amount of prime numbers, you can't generate a infinite amounts of nodes for a link list to represent them all. You're basically attacking the use of arrays for prime numbers because it can't be used to hold an infinite amount of prime numbers. How is that not strawman?

>> No.1546499

>>1546476
Because with an array, you'll have to allocate a block of memory in front that you aren't yet using and may well never use, unless you know in advance how many memory you'll need (which is not the case here).

>> No.1546513

>>1546493
No, he is not. He's only attacking your claim that
>With some creative thinking you can use a set of arrays to hold the prime numbers.
which is in fact wrong for this reason.

>> No.1546517

>>1546493
I never said that you could hold all the primes in a linked list. And I didn't criticize the use of an array. Learn to read.

>> No.1546521

>>1546499
You can allocate memory for a set of pointers to nonexistent arrays and then create them and allocate memory for them when necessary.

>> No.1546525

>>1546499
>unless you know in advance how many memory you'll need (which is not the case here).
What makes you think we can't estimate the number of primes we'll need?

>> No.1546527

>>1546476
Because as numbers get big the amount of primes between two integers shrinks.

>> No.1546529

>>1546521
Still a finite set of pointers, I suppose.

>> No.1546534

For the sieve, why not just allocate an array with room for num/ln(num) elements?

>> No.1546538

>>1546525
Because you probably want a solution with which you can generate primes ad infinitum efficiently, which requires the ability to STORE primes ad infinitum.

>> No.1546539

>>1546517
I never said the arrays could hold all the prime numbers. If you're weren't replying for reason of saying that I implied that arrays could, then that reply was pointless.

>> No.1546548

>>1546529
But still better than a finite set of pointers.

>> No.1546551

>>1546539
>With some creative thinking you can use a set of arrays to hold the prime numbers.

Sounds like ya did.

>> No.1546552

>>1546539
>With some creative thinking you can use a set of arrays to hold the prime numbers.
>the prime numbers
>infinite list
Looks like you did say it after all.

>> No.1546562

>>1546548
>finite set of pointers
>better than a finite set of pointers
wat