I want to write a loop to check for prime numbers. So I'm going to check only numbers ending with 1,3,7,9.
So I need a loop that will increment with 2,4,2,2 and again 2,4,2,2...
What king of loop is best, a 'for loop' or a 'while' with switches in it or something else?
Basically I need to increment three times with 2 and then with 4, three times with 2 and then with 4...
Last edited by Ducky; 12-09-2013 at 12:43 PM.
Using Windows 10 with Code Blocks and MingW.
Don't bother: starting from 3, increment by 2. Then, in your trial division, check for 5 as a divisor. You will be checking for 3 anyway, so that isn't a problem. What this gains you is not having to check for 2 as a divisor.
Note that trial division only requires checking with primes as divisors.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Something like this could work.
Code:int inc[]={2,4,2,2}; for(int x=??,i=0; ?? ; x+=inc[i++%4]){}
Last edited by manasij7479; 12-09-2013 at 01:29 PM.
OK, thanks Laserlight. So you don't think that there is any gain in speed in my method vs checking every number for 5 as a divisor? Not even when you're looking for a long series of big prime numbers?
Using Windows 10 with Code Blocks and MingW.
Yes, that's a good solution. Thanks Manasij!
Using Windows 10 with Code Blocks and MingW.
If you want a significant gain in speed, then consider changing algorithm, e.g., implement the Sieve of Eratosthenes, or use that sieve algorithm to obtain all the possible prime divisors for the range you're looking at, and then use perfect trial division.
As to whether you will actually get a gain in speed from skipping multiples of 5 without testing them as opposed to testing them and then quickly moving on (just two tests: 3 then 5), that should be determined by testing with timing.
Last edited by laserlight; 12-09-2013 at 03:26 PM.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
If you actually want performance, then the fastest way to test if a small number (with say 4 digits or less) is to have a hard coded list of prime numbers.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Sorry?
If you have a hard coded list of prime numbers what are you going to test for?
Using Windows 10 with Code Blocks and MingW.
Whether a larger number is prime, using the numbers in that list as trial divisors.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
You test if the number the user enters is in the list.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
