It looks like they are mapping 0 to 1, etc.
I'm not sure about the code which sets the first 2 numbers as not prime though, that would suggest 1 and 2 are not prime. I agree that 1 is not prime. I'm sure that 2 is prime though ;)
You could always use 101 length vectors and just ignore element 0, you would be less likely to make a silly error then.
I'm still advocating running through the algorithm on a piece of paper before starting coding (looks like it is a bit late for that now though)...
Oh, editing is broken for me now as well.
I was going to suggest once you get it working with a 101 element array rewrite it to use only a 100 element array and map 0 to 1, etc. But do that after you have a working implementation to compare the output against. Later on you could also be clever and not store plausible_prime entries for even numbers (output 2 as the first prime and then no other even numbers after that are prime so you don't really need to remember whether they were prime or not).
EDIT: Test edit...
I've been having bugs on this site this evening, but it isn't letting me start a thread in Comments & Suggestions about them, it just looks like it is loading a page and then never finishes (or it is taking far too long to generate the new post form).
Writing it down on paper was a great idea.
Perhaps the algorithm should be something more like this?
not_prime = p * p;
plausible_prime[not_prime] = false;
while (not_prime <= 100)
{
not_prime += p;
plausible_prime[not_prime] = false;
}
Try it out.
If you type
primes <= 100
into wolframalpha you get this:
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 (25 primes)Changed the code a bit and checked some stuff. I think the algorithm looks good now, but visual studio still gives me: "error C2440: 'return' : cannot convert from 'std::_Vb_reference<_Alloc>' to 'bool &'". Whenever I try to debug it tells me there were build errors and if I ignore it the app crashes and it says something like "Range_error at memory location...".
#include "../../std_lib_facilities.h"
int main()
{
vector<bool>plausible_prime(100, true);
plausible_prime[0] = false;
plausible_prime[1] = false;
for (int p = 2; p < 100; ++p)
for (int not_prime = 2; not_prime < 100;)
{
not_prime += p * p;
plausible_prime[not_prime] = false;
while (not_prime <= 100)
{
not_prime += p;
plausible_prime[not_prime] = false;
if (not_prime >= 100){
if (plausible_prime[p+1] != false)
++p;
else if (plausible_prime[p+1] == true){
for (int v = 1; plausible_prime[p+v] == false;)
p += v;
}
}
}
}
for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] == true)
cout << i+1 << " is prime." << endl;
}
keep_window_open();
}
Also, it's still printing 1 (repeatedly).
Thanks a lot for the help you've given me! I'm going to sleep for now.
Don't ignore build errors. If there's a build error and you ignore it then VS will simply run the last working version (the incorrect one which prints all 1's). Which I consider to be absolutely retarded behaviour but anyway. You need to fix that error before it'll run. I'm not too sure what the problem is but it seems to be coming from the vector<bool> implementation. It works fine here on gcc (as far as compilation goes - the algorithm is still not quite correct) so it looks like a MSVC quirk (your compiler). Try this instead to initialize the vector and see if it makes a difference:
vector<bool> plausible_prime(100);
plausible_prime[0] = false;
plausible_prime[1] = false;
for (int i = 2; i < plausible_prime.size(); ++i) plausible_prime[i] = true;
Also, the "not_prime = p * p" line doesn't look quite right. You need to tick off multiples of whatever prime you found, so you should start from your prime P and then mark 2 * P, 3 * P, ... as non-prime until you reach 100.
You can start at p*p because other multiples of p will have already been crossed off the list.
e.g. when you discover 5 is a prime, 2*5, 3*5, 4*5 will already have gone because you crossed off all multiples of 2, 3 and 4 in an earlier stage.
It looks like you are accessing elements outside the array range to me. These lines look potentially dodgy
if (plausible_prime[p+1] != false)
++p;
else if (plausible_prime[p+1] == true){
for (int v = 1; plausible_prime[p+v] == false;)
p += v;
Also, which line is the error about the vector<bool> occuring? The implementation of vector<bool> can be a bit weird, since the bools are packed into bitfields, try changing it to vector<int> instead, for now at least.
#include <iostream>
#include <vector>
long const N = 100;
int main() {
std::vector<bool> v(N, true);
v[0] = v[1] = false;
std::vector<long> primes;
for (long p=0; p<N; ++p) {
if (v[p]) {
primes.push_back(p);
for (long i=p*p; i<N; i+=p)
v[i] = false;
}
}
for (long p : primes)
std::cout << p << '\n';
}I think the idea is for the OP to do the exercise and learn some stuff, rather than just be given the answer ;)
In your solution though (so indices correspond directly to the numbers):
I wouldn't bother with a second vector to hold the primes, I'd just loop through v (terrible variable name though) and output i if v is true. You can also do the output in the if(v
) loop, so you don't need to loop through the vector again.
EDIT: Although I didn't see this bit in the OP
"Also, I must use a vector to store the prime numbers."
so perhaps an extra vector is required just to hold the primes after all.
I think the idea is for the OP to do the exercise and learn some stuff, rather than just be given the answer ;)
But I think he was a little bit too lost. I tried to write the code in the most straight-forward way I could.EDIT: Although I didn't see this bit in the OP
"Also, I must use a vector to store the prime numbers."
so perhaps an extra vector is required just to hold the primes after all.
