C++

Forum

 
 
The Sieve of Eratosthenes Algorithm

JJRR26 (4)
Hello,

The algorithm consist in that the user give a number (n) and the program have to find the prime numbers and the multiples of it, and when it finds the multiple the program delete the multiple number.

here is a link for more information:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


The problem is that when it gets a multiple, I dont know how to avoid the number for the next prime, for example:

2 is prime and is multiple of 12, but I dont know how to avoid 12 when I am looking the multiples numbers of 3 that is a prime number too.

I will be so grateful if someone can help me becuase I have been yesterday and today trying to do it.

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
#include <iostream>

using namespace std;

int ssys(int user_n);

int main() {
    int user_n;
    cout << "Enter a number: ";
    cin >> user_n;
    cout << "Your Sieve of Eratosthenes algorithm is:\n" << ssys(user_n);
    
    system("pause");
    return 0;
}

int ssys(int user_input){
    int x;
    int number_array[user_input];
    for (int i = (user_input - 1); i > -1; i--){
         number_array[i] = i+1;
         }
         
    //For 2 to be a prime number
    for (int i = 1; i < user_input; i++){
        x = 0;
        for (int j = 1; j < i; j++){
            if (number_array[i]%j == 0){
                x = 1;
                if (number_array[i] == 2){x = 0;}
                }
        }
        if (x == 0){
            cout << number_array[i] << " is a prime number\n";
            
//------------------------Find Multiples------------------------

            for (int p = i; p < user_input; p++){
            x = 0;
            if (number_array[p]%number_array[i] == 0){
                x = 1;
                }
        if (x == 1){
            cout << number_array[p] << " is a multiple of " << number_array[i] << endl;
                    }
            }
        }
        }
            
    //For rest to be a prime number
    for (int i = 2; i < user_input; i++){
        x = 0;
        for (int j = 2; j < i; j++){
            if (number_array[i]%j == 0){
                x = 1;
                if (number_array[i] == 2){x = 0;}
                }
        }
        if (x == 0){
            cout << number_array[i] << " is a prime number\n";
            
//------------------------Find Multiples------------------------

            for (int p = i; p < user_input; p++){
            x = 0;
            if (number_array[p]%number_array[i] == 0){
                x = 1;
                }
        if (x == 1){
            cout << number_array[p] << " is a multiple of " << number_array[i] << endl;
                    }
            }
        }
        }
    




}
cire (8284)
2 is prime and is multiple of 12, but I dont know how to avoid 12 when I am looking the multiples numbers of 3 that is a prime number too.

This is described by the algorithm. There is even pseudo-code describing an implementation in the link you provided.
helios (17575)
2 is a divisor of 12.

I dont know how to avoid 12 when I am looking the multiples numbers of 3 that is a prime number too.
A number getting marked more than once doesn't affect the result of the algorithm.
JJRR26 (4)
Sorry, 2 is a divisor of 12.

I know that it does not affect the algorithm, however I want it to print something like this.

User Number: 13

Print:

2 is a prime number.
4 is multiple of 2.
6 is multiple of 2.
8 is multiple of 2.
10 is multiple of 2.
12 is multiple of 2.
3 is a prime number.
9 is multiple of 3.
5 is a prime number.
7 is a prime number.
13 is a prime number


Without saying:
6 is multiple of 3, 12 is multple of 3 and 10 is multiple of 5, because it was said first that it was multiple of 2.


cire (8284)
I would work on getting the algorithm correct first, although achieving this output should be trivial if you do it while generating the sieve.

There should be no division or modulo operations in your code.
giblit (3750)
There should be no division or modulo operations in your code. +1

All the sieve of Eratosthenes is something like this:

0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10 //removed 2's: 4 6 8 10
0 1 2 3 4 5 6 7 8 9 10 //removed 3's: 9
//5*5 > 10 so no need to go further
Prime: 2 3 5 7


The algorithm I use is a slightly optimized but not fully.

pseudo code:
1
2
3
4
 
for i = 3 to sqrt(N) increment i by 2 <--sqrt(N) is same as i * i < N
    if i is prime
        for j = i * i to N increment j by i
            j is not prime

PS reason I didn't set the 0, 1, or the evens to not prime is because we already know they must be odd so no need to use the extra processing. We can just start at 3 and increment by 2 again when we output the primes. PS you won't be able to output ALL the primes in the sieve so I would output after.

By the way a hint is to use an array of type bool that is size of N + 1 (so we can go from 0->N) or a std::vector<bool>
Last edited on
anup30 (968)
here is your Sieve of Eratosthenes Program.
i have learned some new topics solving this. it took me several hours, but i am glad i could.
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
53
54
55
56
57
 
//Sieve of Eratosthenes
#include <iostream>
#include <vector> //
#include <algorithm> // binary_search(), sort()
using namespace std;
void ssys(int user_n);
bool divisible (int number, int divisor); //
bool prime (int number); //

int main() {
    int user_n;
    cout << "Enter a number: ";
    cin >> user_n;
    cout << "Your Sieve of Eratosthenes algorithm is:\n";
	ssys(user_n);
    
    system("pause");
    return 0;
}

void ssys(int n) {
    vector<int>vec;
    int n1=1, n2=0;
    for(int i=2; i<=n; i++)
        {
        if (prime(i))
            {
            cout << i << " is a prime number." << endl;
            vec.push_back(i);
            while(i*n1 <= n)
                {
                  sort(begin(vec), end(vec));
                  if(!binary_search(begin(vec),end(vec), i*n1) )
                  {
                   cout << i*n1 << " is multiple of "<< i << endl;
                   vec.push_back(i*n1);
                  }					  
                  n1++;
                }
            n1=1;  	
         }
//else { }		  
        }
return;	   
}

bool prime (int number) {
 for ( int i = 2; i < number; i++)
 {  if ( divisible( number, i ) )
       return false;   
 }  
return true;
}

bool divisible (int number, int divisor) {
 return number % divisor == 0;
}
giblit (3750)
here is your Sieve of Eratosthenes Program.
i have learned some new topics solving this. it took me several hours, but i am glad i could.
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
53
54
55
56
57
 
//Sieve of Eratosthenes
#include <iostream>
#include <vector> //
#include <algorithm> // binary_search(), sort()
using namespace std;
void ssys(int user_n);
bool divisible (int number, int divisor); //
bool prime (int number); //

int main() {
    int user_n;
    cout << "Enter a number: ";
    cin >> user_n;
    cout << "Your Sieve of Eratosthenes algorithm is:\n";
	ssys(user_n);
    
    system("pause");
    return 0;
}

void ssys(int n) {
    vector<int>vec;
    int n1=1, n2=0;
    for(int i=2; i<=n; i++)
        {
        if (prime(i))
            {
            cout << i << " is a prime number." << endl;
            vec.push_back(i);
            while(i*n1 <= n)
                {
                  sort(begin(vec), end(vec));
                  if(!binary_search(begin(vec),end(vec), i*n1) )
                  {
                   cout << i*n1 << " is multiple of "<< i << endl;
                   vec.push_back(i*n1);
                  }					  
                  n1++;
                }
            n1=1;  	
         }
//else { }		  
        }
return;	   
}

bool prime (int number) {
 for ( int i = 2; i < number; i++)
 {  if ( divisible( number, i ) )
       return false;   
 }  
return true;
}

bool divisible (int number, int divisor) {
 return number % divisor == 0;
}
o.O

I prefer a sieve like:
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
 
#include <iostream>
#include <vector>

int main()
{
    unsigned largestPrime = 0u;
    std::cout << "Please enter largest prime[2-N]: ";
    std::cin >> largestPrime;
    
    std::vector<bool> sieve(largestPrime+1, true); //0-N
    
    for(unsigned i = 3u; i * i < largestPrime; i += 2)
    {
        if(sieve.at(i))
        {
            for(unsigned j = i * i; j <= largestPrime; j += i)
            {
                sieve.at(j) = false;
            }
        }
    }
    
    unsigned primes = 1u;
    std::cout << "Primes: \n2 ";
    for(unsigned i = 3; i <= largestPrime; i += 2)
    {
        if(sieve.at(i))
        {
            std::cout << i << ' ';
            ++primes;
        }
    }
    
    std::cout << "\nNumber of primes from [2-" << largestPrime << "]: " << primes << std::endl;
    
    return 0;
}
 
Please enter largest prime[2-N]: 100
Primes: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
Number of primes from [2-100]: 25
anup30 (968)
my code outputs, exactly what JJRR26 asked...
2 is a prime number.
4 is multiple of 2.
6 is multiple of 2.
8 is multiple of 2.
10 is multiple of 2.
12 is multiple of 2.
3 is a prime number.
9 is multiple of 3.
5 is a prime number.
7 is a prime number.
13 is a prime number


if user input is 13
giblit (3750)
No one said it didn't the
o.O
was that you did the entire assignment for them, and the indentation hurt my eyes a little bit.
JJRR26 (4)
anup30

Thanks you very much, I found an error that comes here:

sort(begin(vec), end(vec));


because it says that begin() and end() are not declare.

However, I think I can't use this code because it has things that I havent study like Vectors. But thanks you very much, I got some ideas from your code and from giblit code too.

Thanks you anup30 and giblit.
anup30 (968)
OK, i got why giblit differs. i just saw the Wikipedia page of the sieve. the intention of the sieve is to 'sieving' prime numbers in range - by 'sieve method' rather than other prime algorithm. so don't use the prime function i used!
i had read in a book: "programmers will work the exact you asked for" so did i for the comment
JJRR26 (3)
however your code conforms to the concept of the sieve.
JJRR26 (4)
Here is my finished code, because I cant delete in arrays, I organized them at the begining of the Array the prime numbers, If there is a way to reduce the array size, I will be grateful for showing me how. Also if there is a better way to do my code, It will be a pleasure to know it, because there is always a better way!

Thanks everyone for helping me. 

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
53
54
55
56
57
58
59
60
 
#include <iostream>

using namespace std;

int ssys(int user_n);

int main() {
    int user_n;
    cout << "Enter a number: ";
    cin >> user_n;
    cout << "Your Sieve of Eratosthenes algorithm is:\n" << endl;
    ssys(user_n);
    
    
    system("pause");
    return 0;
}

int ssys(int user_input){
    int x;
    int n=2;
    int number_array[user_input];
    for (int i = (user_input - 1); i > -1; i--){
         number_array[i] = i+1;
         }
         
    //Find prime number
    for (int i = 1; i < user_input; i++){
        x = 0;
        for (int j = 2; j < i; j++){
            if (number_array[i]%j == 0){
            x = 1;
                }
        if (number_array[i] == 2){x = 0;}
        }
        if (x == 0){
            cout << number_array[i] << " is a prime number\n";
            if(n<=i){
                    number_array[n]=number_array[i];//moving the prime numbers to the new position
                    n=n+1;
                    }
    //Find multiples of the number                
            for (int p = i; p < user_input; p++){
            x = 0;
            if (number_array[p]%number_array[i] == 0){
                x = 1;
                }
        if (x == 1){
            cout << number_array[p] << " is a multiple of " << number_array[i] << endl;
                    }
            }
        }
        }
    
    cout << "Your prime numbers are oreganized from lowest to highest from the position 0 to " << n-1 << ". \n";
        
    for(int w=0; w<n; w++){//Showing the prime numbers
            cout << number_array[w] << " "; 
            }
}
Last edited on
giblit (3750)
That's not even a sieve of Eratosthenes. I think you should look at my example and the wiki article again.
http://www.cplusplus.com/forum/beginner/143526/#msg757265
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The image on wiki also helps you visualize it if that helps.
http://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif
anup30 (968)
@ JJRR26, as i mentioned earlier you cannot use any random number algorithm other than sieve of Eratosthenes algorithm.

int number_array[user_input];

although, supported by gcc compiler, wont work in visual studio.
it has to be an unsigned integer.
to initialize variable sized array:

int* number_array = new int [user_input]; //dynamic memory allocation

and remember to delete it after usage: delete[] number_array
Topic archived. No new replies allowed.