#include <cstdio>
#include <vector>
#include <cmath>
#define MAX 16001
using std::vector;
int main()
{
constint Counter = 10;
int temp = MAX;
vector<int> Sieve(MAX, 1);
printf ("Size of vector is %d\n", int (Sieve.size()));
for (int C = 0; C < MAX ; C += 2)
if (!(C % 2) && C > 0)
{
Sieve.at(C - 2)= 0;
--temp;
}
bool GotMAX = false;
for (int T = 3; !GotMAX ;T += 2)
for (int A = 2, Y = (T*A); (Y+2) < MAX; ++A)
{
if ((Sieve.at(Y - 2)))
{
Sieve.at(Y - 2) = 0;
--temp;
}
Y = (T*A);
if (temp - Counter <= 0)
{
puts ("This worked!\n");
int Prime = 2; //We know that the first prime number was 2
int E = Counter;
while(E > 0)
{
if (Sieve.at(Prime -2))
--E;
++Prime;
}
printf("%d\n", Prime);
GotMAX = true;
break;
}
}
return 0;
}
I'm sure the code is self explanatory, but incase you don't see it immediately, it is a prime finder; and I am trying to implement the Sieve of Eratosthenes.
Don't used signed variables when you only want to deal with unsigned values.
There comes a point where Y is equal to 2147483646, and Y+2 is -2147483648 due to overflow when the addition is done. That means that on line 26, (Y+2) < MAX will be true when it shouldn't be, and you will access memory that is out of the bounds of your vector, Sieve in the body of the for loop.
Thanks for the response, but the maximum I will be going to will be 16001 so this will not ever (never) exceed the limit of 'int'. When I look for larger numbers then I will look into more suitable variable types.
Still open for ideas guys! Why is my code not working?
Thanks for the response, but the maximum I will be going to will be 16001 so this will not ever (never) exceed the limit of 'int'.
You just keep guessing at what your code is doing then.
It may be that it shouldn't go that high, but the fact is it does, and the reason you don't detect is that you're using the wrong type for your variables (and probably the wrong condition for your loop.)
But if you don't actually want help, I'll keep quiet. =P
You just keep guessing at what your code is doing then.
I don't know any other way of determining the ith prime using this method other than having if check a large enough range large enough to contain that prime. If you have any ideas, I am open
I don't know any other way of determining the ith prime using this method other than having if check a large enough range large enough to contain that prime.
Using a sieve is reasonable. But you aren't implementing it correctly, and as near as I can tell you're not making any attempt to debug it. You're just counting on the people who read these boards to do that for you.
This is the ouput for your code when I change MAX to 20:
Size of vector is 20
This worked!
22
Maybe you can trace through the logic and figure out what's going on?
#include <iostream>
#include <vector>
#define MARK 1000000//ith prime
usingnamespace std;
/*
Trying to implement a prime sieve. This is a work in progress
*/
int main()
{
constint ThisSize = MARK;
vector<bool> Sieve(ThisSize, true);
int counter = 0;
bool checkingTime = false;
int s = 1;
unsigned b = 2;
while (1)
{
unsigned w = 3;
for (unsigned a = 2; a*b <= (unsigned)(Sieve.size()); ++b)
if (Sieve.at(a*b - 1))
Sieve.at(a*b - 1) = false;
while (!checkingTime)
{
for (unsigned q = 2, Prod = w * q; Prod < (unsigned)Sieve.size() ; ++q, Prod = w * q)
if (Sieve.at(Prod - 1))
Sieve.at(Prod - 1) = false;
if (w > (unsigned)Sieve.size()/2)//Make sure we have checked all the values we have
checkingTime = true;
w+=2;
}
if (checkingTime)
for ( ;counter < ThisSize && s < (int)Sieve.size(); ++s)
if (Sieve.at(s))
{
++counter;
if (counter == ThisSize)
{
cout << s+1 <<endl;
break;
}
}
if (counter == ThisSize)
break;
else
{
checkingTime = false;
Sieve.resize(Sieve.size() + ThisSize, true);
}
}
return 0;
}
Tweaked it a bit more, eliminated some bugs, introduced a few other bugs. Now finds 10 millionth in 14 secs!
#include <iostream>
#include <vector>
#define MARK 10000000//ith prime
usingnamespace std;
/*
Trying to implement a prime sieve. This is a work in progress
*/
int main()
{
constint ThisSize = MARK;
vector<bool> Sieve(ThisSize, true);
vector<unsigned> Helper(ThisSize, 2);
int counter = 0;
bool checkingTime = false;
int s = 1;
unsigned b = 2;
while (1)
{
unsigned w = 3;
int h = 0;
for (unsigned a = 2; a*b <= (unsigned)(Sieve.size()); ++b)
if (Sieve.at(a*b - 1))
Sieve.at(a*b - 1) = false;
while (!checkingTime)
{
unsigned q = Helper.at(h);
for (unsigned Prod = w * q; Prod < (unsigned)Sieve.size() ; ++q, Prod = w * q)
if (Sieve.at(Prod - 1))
Sieve.at(Prod - 1) = false;
Helper.at(h++) = q;
if (w > (unsigned)Sieve.size()/2)//Make sure we have checked all the values we have
checkingTime = true;
w+=2;
}
if (checkingTime)
for ( ;counter < ThisSize && s < (int)Sieve.size(); ++s)
if (Sieve.at(s))
{
++counter;
if (counter == ThisSize)
{
cout << s+1 <<endl;
break;
}
}
if (counter == ThisSize)
break;
else
{
checkingTime = false;
Sieve.resize(Sieve.size() + ThisSize, true);
Helper.resize(Helper.size() + ThisSize, 2);
}
}
return 0;
}