Need help creating prime number program

This is a discussion on Need help creating prime number program within the C++ Programming forums, part of the General Programming Boards category; I have an assignment saying I need to use the Sieve of Eratothenes to figure out which nubmers are prime ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    6

    Need help creating prime number program

    I have an assignment saying I need to use the Sieve of Eratothenes to figure out which nubmers are prime from 1-499.

    "One method for finding all prime numbers in the range from 1 - n is known as the Sieve of Eratosthenes. Consider the list of numbers from 2 - n. Two is the first prime number, but the multiples of 2 (4,6,8,...) are not, and so they are crossed out in the list. The first number after 2 that was not crossed out is 3, the next prime. We then cross from the list all higher multiples of 3 (6,9,12,...). The next number not crossed out is 5, the next prime, and so we cross out all higher multiples of 5 (10,15,20,...). We repeat this process until we reach the first number in the list that has not been crossed out and whose square is greater than n. Use the Sieve of Eratosthenes to list all prime numbers less than or equal to 499.


    Use a constant M = 499

    Use an array of boolean

    The output should be formatted so that each line (except possibly the last) contains exactly 10 primes"

    I'm thinking set every element to true. Then, if it is a multiple of 2, make it false, if it is a multiple of 3 make it false... and so on.

    I tried

    Code:
    for(int i = 1; i <= M; i++)
    		prime[i] = true;						
    
    	for(i = 2 ; i <= M; i++)					
    		for(int j = 1; j <= M; j++)		
    			if(j % i == 0 ) prime[j] = false;
    But that makes every j value that is divisible by the i value false.... so when a prime is divided by itself, it turns to false.

    Any suggestions?

  2. #2
    Webhead Spidey's Avatar
    Join Date
    Jul 2009
    Posts
    285
    I'm thinking set every element to true. Then, if it is a multiple of 2, make it false, if it is a multiple of 3 make it false... and so on.
    Exactly, but you must remember that if an element has been marked false, it will always remain false and need not be checked again.

    But that makes every j value that is divisible by the i value false.... so when a prime is divided by itself, it turns to false.
    Why not add a simple check to see if i != j ?

  3. #3
    Registered User
    Join Date
    Jul 2009
    Posts
    6
    Quote Originally Posted by Spidey View Post
    Why not add a simple check to see if i != j ?
    Oh my god, I feel like an idiot. That fixed it ha ha... Thanks! Hurray for wasting a thread!

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    for(i = 2 ; i <= M; i++)					
    		for(int j = 1; j <= M; j++)		
    			if(j % i == 0 ) prime[j] = false;
    A hint: you don't have to increment the for loop variable in steps of 1.

    You should also do this for only prime numbers (if you have crossed out multiples of 2, crossing out multiples of 4, 6, 8 etc would be a waste of time).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    Quote Originally Posted by anon View Post
    Code:
    for(i = 2 ; i <= M; i++)					
    		for(int j = 1; j <= M; j++)		
    			if(j % i == 0 ) prime[j] = false;
    A hint: you don't have to increment the for loop variable in steps of 1.

    You should also do this for only prime numbers (if you have crossed out multiples of 2, crossing out multiples of 4, 6, 8 etc would be a waste of time).
    FOr that matter, j can also start at i*i:
    Code:
    		for(int j = i*i; j <= M; j+=i)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 11:06 AM
  2. Issue w/ Guess My Number Program
    By mkylman in forum C++ Programming
    Replies: 5
    Last Post: 08-23-2007, 01:31 AM
  3. Replies: 7
    Last Post: 08-19-2007, 08:10 AM
  4. problem with my prime number program
    By datainjector in forum C Programming
    Replies: 4
    Last Post: 07-12-2002, 12:30 PM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21