C++ Help

[DerpOverlord]

As a project for my computer science class, I need to write a program that prompts the user to enter a positive integer. Then the program needs to display all the prime numbers between 3 and n. The best lead I got onto this was the Sieve of Eratosthenes. The problem is I do not know how to create that with just the iostream library. Can anyone help?

solved

[giblit]

Primes start with 2 not 3 FYI.

Though creating a Sieve of Eratosthenes is pretty straight forward. In your case you said with only iostream so you are going to need to use raw pointers and allocate enough space.

The key thing you will need is an array of booleans. (0 = not prime, and 1 = prime).


There is a pretty good image of how you would do it on http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


The basic algorithm is something like

bool primes[largest+1]; //or bool *array = new bool[largest + 1];
//if its more than a few hundred thousand you may want to make it global
//so you don't run out of stack memory

for(int i = 3; i * i <= largest; i += 2)
{
    if(primes[i])
    {
        for(int j = i * i; j <= largest; j += i)
        {
            primes[j] = false;
        }
    }
}


std::cout << 2 << ' ';
for(int i = 3; i <= largest; i += 2)
{
    if(primes[i]) std::cout << i << ' ';
}

std::cout << std::endl;

EDIT I noticed your first attempt this is how you check if it is prime or not

if(i % 2 != 0)
{
cout<< i << "\n";
}

which is really flawed. This means every odd number is prime such as 9, 15, 21, 25 which are not prime.

[DerpOverlord]

My teacher wants it to start at 3. What would I need to change for that to work

[giblit]

Don't output 2 and there is no even number that is a prime so you can just start by 3 and increment by 2 checking if it is a prime since that would only check odds.

if you are talking about the code I provided to show you the Sieve in action then you simply would not output 2 :P

[DerpOverlord]

I do not completely understand the code that is typed above. Could you some what explain what is happening in the code?

[giblit]

Have you looked at the wikipedia link? It explains the algorithm, it even has an image that narrates the algorithm.

[DerpOverlord]

I read it but I do not understand C++ to understand some of the things of the code you typed in. For example: bool primes[largest+1];
I do not understand why there are brackets on that

[DerpOverlord]

I think I'll try making my own version by using the wikipedia page as a guide and I'll reply anything else if I run into any problems I don't understand. Anyways, thank you for the link.

[giblit]

That is an array. You can't really make a sieve without an array :P

If you can't use arrays you may have to brute force it with something like this (not effective or pretty)

for(int i = 3; i <= largest; i += 2)
{
    bool prime = true;
    for(int j = 3; j * j <= i && prime; j += 2)
    {
        prime = i % j;
    }
    if(prime) std::cout << i << ' ';
}

[DerpOverlord]

so basically sieving in C is using a ton of restricting lines to get the correct data?

[giblit]

Well, you just need to create the list to store what are prime and what are not prime.


Here is the basic algorithm

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
Initially, let p equal 2, the first prime number.
Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked).
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3. 

[DerpOverlord]

okay but since i need to display separately should I make a variable that displays once and changes. Like if i had variable 'i', I can change it from 1 and it will cout 1 and i change it to 2, it will cout 2?

[DerpOverlord]

I tried your array and it worked and I understood it after I ran it. Thank you!