Thread: Looping with different values

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    916

    Looping with different values

    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.
    Windows 10 with Visual Studio 14.0.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,727
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    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.

  4. #4
    Registered User
    Join Date
    Dec 2007
    Posts
    916
    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?
    Windows 10 with Visual Studio 14.0.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    916
    Quote Originally Posted by manasij7479 View Post
    Something like this could work.
    Code:
    int inc={2,4,2,2};
    for(int x=??,i=0; ?? ; x+=inc[i++%4]){}
    Yes, that's a good solution. Thanks Manasij!
    Windows 10 with Visual Studio 14.0.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,727
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    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.

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    916
    Sorry?

    If you have a hard coded list of prime numbers what are you going to test for?
    Windows 10 with Visual Studio 14.0.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,727
    Quote Originally Posted by Ducky
    If you have a hard coded list of prime numbers what are you going to test for?
    Whether a larger number is prime, using the numbers in that list as trial divisors.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Quote Originally Posted by Ducky View Post
    Sorry?

    If you have a hard coded list of prime numbers what are you going to test for?
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 12-10-2013, 02:29 AM
  2. Replies: 16
    Last Post: 08-22-2013, 12:37 AM
  3. Replies: 13
    Last Post: 07-27-2013, 10:20 AM
  4. write() and read() int values from socket returning wrong values.
    By Premjith P S in forum Linux Programming
    Replies: 8
    Last Post: 11-29-2012, 02:59 PM
  5. I need help with looping lowest priority values first
    By spendotw in forum C Programming
    Replies: 21
    Last Post: 01-18-2012, 03:36 PM