Calculating prime numbers

[rtzoeller]

Hello,

I have recently begun working on the Euler Problems and need to find prime numbers from 2 up to a user selected number. The code I have so far is:

#include <iostream>
#include <vector>
using namespace std;

int main ()
{
    vector<unsigned int> primeNumbers;
    vector<unsigned int>::iterator iter;
    primeNumbers.push_back(2);
    int upperLimit;
    cin >> upperLimit;
    int temp;
    for (int i = 3; i < upperLimit; i++) // Check for prime numbers from 3 through upperLimit
    {
        temp = 0;
        for (iter = primeNumbers.begin(); iter < primeNumbers.end(); iter++ ) // Iterate through the vector of prime numbers
        {
            if ((i % *iter) != 0) // If not prime stop testing
            {
                break;
            }
            temp++;
        }
        if (temp == primeNumbers.size())
        {
            primeNumbers.push_back(i);
        }

    }
    for (int i = 0; i < primeNumbers.size(); i++)
    {
        cout << primeNumbers[i] << " ";
    }
}

In my head it makes sense, but when it is compiled it prints powers of 2 for a reason I don't know.

Where did I go wrong?

Ryan

[packetpirate]

Can you show some of the output?

[jsmith]

The inner loop should be "loop until the candidate number is proven to be prime".
However, the if statement, which breaks out of the for loop, says "stop if i is not divisible by the number", which in other words says, if i is not divisible by 2, then don't bother checking the rest of the numbers.

We'll start there; the algorithm in general is wrong.

[cheeordie]

I think if you turn
if((i % *iter) != 0)
into
((i % *iter) == 0)
it should work. You want to break if it is divisible by a prime because then it is not prime. Otherwise everything else looks fine.
Your program doesn't include the upper bound at the moment. That might be the only thing you want to change. If I enter 23 as the upper bound, it does not include it.

[girish1026]

Hi, below I provided the general C code to print prime numbers from 2 to n. I think you may use this logic in ur program.

#include <stdio.h>

int main(void)
{
int i,j,k,n;

printf("Enter a number\n");
scanf("%d",&n);

printf("The prime numbers from 2 to %d are\n",n);

for(i=2;i<=n;i++)
{
k=0;
for(j=1;j<=i;j++)
if(i%j==0)
k++;
if(k==2)
printf("%d ",i);
}

getch();
return 0;
}