C++

Forum

 
Need help in Prime Numbers (Sieve of Eratosthenes method)

Grax (49)
i had an assignment that ask me to find out the prime numbers from 2 to n numbers, and it must used the Sieve of Eratosthenes method to find that...(http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), after i finished coding that refer to the wikipedia website, my program doesn't give the correct result, and i don't know what the problems are, can anyone please help me.... here's my code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

void printPrime(bool isPrime[], const int n );

int main()
{
    int n = 0;
    
    cout << "Enter the N numbers: ";
    cin >> n;
    
    const int N = n;
    bool isPrime[N];
    
    //initialize isPrime to true
    for (int i = 0; i <= n; i++)
        isPrime[i] = true;
    
    cout << "Prime numbers from 2 to " << n << " are \n"; 
    printPrime(isPrime, N);
    
    getch();
    return 0;
}

void printPrime(bool isPrime[], const int n )
{ 
     cout << endl;
     int mul = 2;
     for (int i =2; i <= n/2; i++)
     {
          if (isPrime[i]== true)
          {
             for (int j = mul*i ; j <= n; mul++)
                 isPrime[i] = false;
          }
      } 
      
      cout << endl;
         
      cout << "Prime number:\n";
      for (int i = 2; i <= n; i++ )
      {
          if (i % 10 == 0)
             cout << setw(3) << isPrime[i] << endl;
          else
              cout << setw(3) << isPrime[i] << " ";
      }
}


and the above code i refer to the pseudo code below

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., while i ≤ n/2:
if A[i] is true:
for j = 2i, 3i, 4i, ..., while j ≤ n:
A[j] = false

Now all i such that A[i] is true are prime.
Peter87 (11234)
The size of isPrime is one too small.

This is wrong
1
2
 
for (int j = mul*i ; j <= n; mul++)
	isPrime[i] = false;


You update mul but doing so will never make j <= n false so you will have an infinite loop here.
Grax (49)
1
2
 
for (int j = mul*i ; j <= n; j++ , mul++)
	isPrime[i] = false;


1
2
3
4
5
6
7
8
9
10
11
12
 
      cout << "Prime number:\n";
      for (int i = 2; i <= n; i++ )
      {
          if (isPrime[i] == true)
          {
              if (i % 10 == 0)
                 cout << setw(3) << i << endl;
              else
                  cout << setw(3) << i << " ";        
          }
              
      }


i had change some of me code above... but still not working ...
Last edited on
Grax (49)
what i really want in my code is:

if i = 2, multiple of 2 (4,6,8,10.....) = false
i = 3, multiple of 3 (3,6,9,12 ....) = false
and so on up to n value....

but i don't know how to write it... someone can hlep me please...
Caprico (226)
Try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool isPrime[n];

for (i=1; i<n; i++)
	isPrime[i]=true;		//Initialization of all values to true

for (i=2; i<n; i++)			
{
	if (isPrime[i]=true)
	{
		for (j=i; j<n; j++)
		{
			if (j&i==0&&j!=i)
			isPrime[j]=false;		//Set all multiples of i to false.
		}
	}
}


Haven't run it in a compiler, but it should work..
Grax (49)
1
2
3
4
5
6
7
8
9
 
for (int i =2; i <= n/2; i++)
     {
          if (isPrime[i]== true)
          {
             for (int j = i ; j <= n; j += i)
                 if (j != i)
                    isPrime[j] = false;
          }
      }


i have make some change and it is working now! thanks for all the help! problem solved ^.^
Caprico (226)
Always welcome.. :)
Topic archived. No new replies allowed.