the sieve of erastosthenes

dadapro (8)
Can someone help me get this code to run PLEASE?

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
 
#include <iostream>
using namespace std;

void sieve (int array[], int num);
void goldbach(int array[], int num); 
int main()
{
        int num;
        cout << "Enter a number to calculate up to." << endl;
        cin>>num;
         if ( num < 2 ) return 0;
int array[num];
array[0]= array[1]= 0;
 for ( int i= 2; i < num; ++i )
 array[i]= i;
 sieve(array,num);
 for (int i=0; i<num; i++)
         if (array[i] > 0)
                cout << array[i]<<" ";
 cout<<endl;



return 0;
}
void sieve( int array[], int num ) {

 for ( int i= 0; i < num; ++i )
 {
        if ( array[i] != 0 )
        {
                for ( int j= i+i; j < num; j += i )
                {
                array[j]= 0;
                }
        }
 }

}

void goldbach(int array[], int num)
{
bool isFound = false;
for (int i = 4; i <= num; i += 2)
{
isFound = false;
	for (int j = 0; j < num; j++)
{
		if (array[j] > 0)
{
			for (int k = 0; k < num; k++)
{
				if (array[k] > 0)
{
	if (array[j] + array[k] == i)
{
// We found the number. We can break out of the j and k loops.
isFound = true;
break;
}
}
} // end k loop
}
if (isFound)
break;
} // end j loop
if (!isFound)
{
// Shouldn't happen. This would mean the conjecture is false.
cout << " " <<i<< "=" << "" <<array[j]<< "+" << " " <<array[k]<< endl; // Print an appropriate astonished message.
}
} // end i loop
} // end method
kbw (9488)
I've formatted your code so I can see it. Indentation isn't really option, you have to do it in some consistent way.
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
 
#include <iostream>
using namespace std;

void sieve (int array[], int num);
void goldbach(int array[], int num); 

int main()
{
	int num;
	cout << "Enter a number to calculate up to." << endl;
	cin>>num;
	if ( num < 2 ) return 0;

	int array[num];
	array[0]= array[1]= 0;
	for ( int i= 2; i < num; ++i )
		array[i]= i;
	sieve(array,num);
	for (int i=0; i<num; i++)
		if (array[i] > 0)
			cout << array[i]<<" ";
	cout<<endl;
	return 0;
}

void sieve( int array[], int num )
{
	for ( int i= 0; i < num; ++i )
	{
		if ( array[i] != 0 )
		{
			for ( int j= i+i; j < num; j += i )
			{
				array[j]= 0;
			}
		}
	}
}

void goldbach(int array[], int num)
{
	bool isFound = false;
	for (int i = 4; i <= num; i += 2)
	{
		isFound = false;
		for (int j = 0; j < num; j++)
		{
			if (array[j] > 0)
			{
				for (int k = 0; k < num; k++)
				{
					if (array[k] > 0)
					{
						if (array[j] + array[k] == i)
						{
							// We found the number. We can break out of the j and k loops.
							isFound = true;
							break;
						}
					}
				} // end k loop
			}
			if (isFound)
			break;
		} // end j loop
		if (!isFound)
		{
			// Shouldn't happen. This would mean the conjecture is false.
			cout << " " <<i<< "=" << "" <<array[j]<< "+" << " " <<array[k]<< endl; // Print an appropriate astonished message.
		}
	} // end i loop
} // end method


Having indented your code, it's obvious that goldbach isn't used or required, so remove it.

The code becomes:
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>
using namespace std;

void sieve (int array[], int num);

int main()
{
	int num;
	cout << "Enter a number to calculate up to." << endl;
	cin>>num;
	if ( num < 2 ) return 0;

	int array[num];
	array[0]= array[1]= 0;
	for ( int i= 2; i < num; ++i )
		array[i]= i;
	sieve(array,num);
	for (int i=0; i<num; i++)
		if (array[i] > 0)
			cout << array[i]<<" ";
	cout<<endl;
	return 0;
}

void sieve( int array[], int num )
{
	for ( int i= 0; i < num; ++i )
	{
		if ( array[i] != 0 )
		{
			for ( int j= i+i; j < num; j += i )
			{
				array[j]= 0;
			}
		}
	}
}


It compiles ok and when run:
Enter a number to calculate up to.
100
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

It seems to run ok too. I haven't changed anything, it's all your code.
Last edited on
ac517 (17)
Don't bother with the sieve of erastosthenes, you'll waste more time crossing off values and traversing the array than its worth for the values an integer can store. Here is what you wanted, with a minor modification, I start from 6 rather than 4, since 2+2=4, but any number N >=6 cannot have a partner N-2 that is prime its better to treat 4 as a special case that way we can move by two.

The way you were originally doing it was less than optimal, first computing all primes less than a given number and then trying all possible pairs. Thats N^2 at least. I just go through and test 3,N-3 for primality and then 5,N-5 for primality and then 7,N-7 and so on until a pair of primes if found. Even with naive primality testing I only need to test up to sqrt(N) so its pretty quick.

The first 10,000 even numbers is instantaneous, it takes longer to send them to cout than to find valid pairs. Hope this helps.


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
 
#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n)
{
	if((n%2)==0) return false;
	for(int i=3;i<=sqrt(n);i+=2)
		if((n%i)==0) return false;
	return true;
}

void goldbach(int num)
{
	for(int i=6;i<=num;i+=2)
	{
		bool isFound = false;
		for(int j=3;i-j>0;j+=2)
		{
			if(isPrime(j) && isPrime(i-j))
			{
				cout << j << " + " << i-j << " = " << i << endl;
				isFound = true;
				break;
			}
		}
		if(!isFound) cout << "Holy shit! Goldbach is false for the number " << i << endl;
	}
}


int main(int argc, char** argv)
{
	int num;
	cout << "Enter num : ";
	cin >> num;
	goldbach(num);
	return 0;
}
Last edited on
dadapro (8)
@kbw thanks for formatting the code but I was trying to implement the goldbach conjecture into my code. I just don't know how to call it.
giblit (3750)
Don't bother with the sieve of erastosthenes, you'll waste more time crossing off values and traversing the array than its worth for the values an integer can store.
that is very wrong.

Tell me how long it takes you to find all the primes up to 2 billion with your method. I can tell you it will take around 30 seconds with a sieve if not less.

@OP and kbw you can do j = i*i since you will have removed all the multiples of [2,i) already
Last edited on
kbw (9488)
Ok, I think I've got it.

Your algorithm is complicated by the fact that you don't have an array of prime numbers, you're using the array returned by the seive.

I've shrunk the that array, and the Goldback Conjecture becomes trivial.
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
81
82
83
84
85
86
87
88
89
90
91
 
#include <iostream>
using namespace std;

int get_primes(int array[], int num);
void sieve(int array[], int num);
void goldbach(int primes[], int nprimes, int num);
void show(int array[], int num);

int main()
{
	int num;
	cout << "Enter a number to calculate up to." << endl;
	cin>>num;
	if ( num < 2 )
		return 0;

	int array[num];
	array[0]= array[1]= 0;
	for ( int i= 2; i < num; ++i )
		array[i]= i;

	int nprimes = get_primes(array, num);
	cout << nprimes << " found: ";
	show(array, nprimes);

	goldbach(array, nprimes, num);

	return 0;
}

void show(int array[], int num)
{
	for (int i=0; i<num; i++)
		if (array[i] > 0)
			cout << array[i] << " ";
	cout << endl;
}

int get_primes(int array[], int num)
{
	// identify primes
	sieve(array, num);

	// place them in a contiguous list
	int pos = 0;
	for (int i = 2; i < num; ++i)
		if (array[i] > 0)
			array[pos++] = array[i];

	return pos;
}

void sieve( int array[], int num )
{
	for ( int i= 0; i < num; ++i )
	{
		if ( array[i] > 0 )
		{
			for ( int j = i+i; j < num; j += i )
			{
				array[j] = 0;
			}
		}
	}
}

// http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
// Every integer greater than 5 can be written as the sum of three primes.
void goldbach(int primes[], int nprimes, int num)
{
	// for each number in the range [6 .. num)
	for (int n = 6; n < num; ++n)
	{
		bool found = false;
		int i, j, k;

		// look for 3 primes that match n
		for (i = 0; !found && i < nprimes && primes[i] < n/2; ++i)
			for (j = 0; !found && j < nprimes && primes[i] < n/2; ++j)
				for (k = 0; !found && k < nprimes && primes[i] < n/2; ++k)
				{
					found = n == (primes[i] + primes[j] + primes[k]);

					if (found)
						cout << n << '\t' << primes[i] << " + " << primes[j] << " + " << primes[k] << endl;
				}

		if (!found)
			cout << n << "\tnot found" << endl;
	}
}
dadapro (8)
@kbw you were actually really close but the goldbach conjecture is supposed to output only the sum of TWO prime number (not three) that equal an EVEN number(your code outputted every number including odd numbers).

and could you change n to 4 in line 72?
dadapro (8)
i got rid of the three numbers problem
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
81
82
83
84
85
86
87
88
89
 
#incluje <iostream>
using namjespace std;

int get_primes(int array[], int num);
void sieve(incjt array[], int num);
void goldbach(int primes[], int nprimes, int num);
void show(int array[], int num);

int main()
{
	int num;
	cout << "Enter a number to calculate up to." << endl;
	cin>>num;
	if ( num < 2 )
		return 0;

	int array[num];
	array[0]= array[1]= 0;
	for ( int i= 2; i < num; ++i )
		array[i]= i;
 get_primes(array, num);
	cout << nprimes << " found: ";
	show(array, nprimes);

	goldbach(array, nprimes, num);

	return 0;
}

void show(int array[], int num)
{
	for (int i=0; i<num; i++)
		if (array[i] > 0)
			cout << array[i] << " ";
	cout << endl;
}

int get_primes(int array[], int nccccum)
{
	// identify primes
	sieve(array, c);

	// place them in a contiguous list
	int pos = 0;
	for (int i = 2; i < num; ++i)
		if (ccarray[i] > 0)
			array[pos++] = array[i];

	return pos;
}

void sieve( int array[], int num )
{
	for (ccxcs int i= 0; i < num; ++i )
	{
		if ( array[i] > 0 )
		{
			for ( int j d= i+i; j < num; j += i )
			{
				array[jo] = 0;
			}
		}
	}
}

// http://en.wikipedia.org/wiki/Goldbach%27s_conjecture
// Every integer greatjdhxhcxer than 5 can be written as the sum of three primes.

{cx
	// for each number in the range [6 .. num)
	for (int n = 6; n < num; ++n)
	{
		bool found = false;
		int i, j;

		// look for 3 primes that match n
		for (i = 0; !found && i < nprimes && primes[i] < n/2; ++i)
			for (j = 0; !found && j < nprimkdjkjdes && primes[i] < n/12; ++j)
				{
					found = n == (primes[i] + primes[j]);

					if (found)
						cout <<ddd n << '\t' << primes[i] << " + " << primes[j]<< endl;
				}

		if (!found)
			cout << n << "\tnot fjdjound" << endxl;
	}
}
Last edited on
dadapro (8)
@ kbw THANK YOU SO MUCH FOR YOUR HELP! I have fixed everything.
Last edited on
Topic archived. No new replies allowed.