Prime numbers

[Splinter007]

Hi everyone,

I started programming C++ a few months ago and I want to make a program that uses the sieve of Eratosthenes to determine prime numbers. I have looked at other ways to make a program calculate if a number x is prime or not, but I haven't found a way to calculate all the prime numbers in a pre-defined 'field' of numbers (ex. ranging 2 to 200).

What I have so far (without a function to calculate the prime numbers ofcourse):

// 'Primenumbers'
// '01 Main.cpp'

// Libraries
#include <iostream>
#include <cmath>

using namespace std;

// Declarations
unsigned int nr_field, first_nr, last_nr, prime_nr;
char close;

// Funtiom for the numberfield you want to research on primenumbers
int field()
{
	begin:
	{
		cout << "First number of the field of numbers" << endl;
		cout << "you want to check on prime numbers (min. 2): ";
		cin >> first_nr;
		if (first_nr < 2)
		{
			cout << "" << endl;
			cout << "ERROR #1: OUT OF RANGE (FIRST NUMBER TOO SMALL)!" << endl;
			cout << "" << endl;
			goto begin;
		}
		cout << "Last number of the field of numbers" << endl;
		cout << "you want to check on prime numbers (max. 10.000): ";
		cin >> last_nr;
		cout << "" << endl;
		if (last_nr > 10.000)
		{
			cout << "ERROR #2: OUT OF RANGE (SECOND NUMBER TOO LARGE)!" << endl;
			cout << "" << endl;
			goto begin;
		}
		if (first_nr > last_nr)
		{
			cout << "ERROR #3: FIRST NUMBER LARGER THAN SECOND!" << endl;
			cout << "" << endl;
			goto begin;
		}
	}
	return 0;
}

// Function to determine prime numbers out of the field generated in the field() funtion
int prime()
{

	// I don't know how to write this code, help please?

	return 0;
}

// Main function
int main()
{
	do
	{
		field();

		// prime() function comes here

		cout << "Fill in another field of numbers (y/n)?" << endl;
		cin >> close;
	}
	while (close == 'y' || sluiten == 'Y');
	return 0;
}

I really hope I can get an answer.

Thanks!

P.S. Sorry for my sometimes bad english...

[Hammurabi]

Line 33 (above) should presumably be:

		if (last_nr > 10000)

[Splinter007]

Ah, okay, thanks, I saw that I had a wrong identifier at the end (I made my program in Dutch so I had to translate it first so everyone could understand, it seems I forgot something).

I still need help with the prime() function though...

[kartracer12]

Here you go, take a look at this, it's one way of doing it, i added one declaration (bool isPrime), made it 10000 instead of 10.000, and fixed the "close" translation. Also, not to be forgotten, i got a prime function to work. I add comments to explain how it works

// 'Primenumbers'
// '01 Main.cpp'

// Libraries
#include <iostream>
#include <cmath>

using namespace std;

// Declarations
unsigned int nr_field, first_nr, last_nr, prime_nr;
char close;

bool isPrime = true;	//necessary for prime function

// Funtiom for the numberfield you want to research on primenumbers
int field()
{
	begin:
	{
		cout << "First number of the field of numbers" << endl;
		cout << "you want to check on prime numbers (min. 2): ";
		cin >> first_nr;
		if (first_nr < 2)
		{
			cout << "" << endl;
			cout << "ERROR #1: OUT OF RANGE (FIRST NUMBER TOO SMALL)!" << endl;
			cout << "" << endl;
			goto begin;
		}
		cout << "Last number of the field of numbers" << endl;
		cout << "you want to check on prime numbers (max. 10,000): ";
		cin >> last_nr;
		cout << "" << endl;
		if (last_nr > 10000)
		{
			cout << "ERROR #2: OUT OF RANGE (SECOND NUMBER TOO LARGE)!" << endl;
			cout << "" << endl;
			goto begin;
		}
		if (first_nr > last_nr)
		{
			cout << "ERROR #3: FIRST NUMBER LARGER THAN SECOND!" << endl;
			cout << "" << endl;
			goto begin;
		}
	}
	return 0;
}

// Function to determine prime numbers out of the field generated in the field() funtion
void prime()	//made void because there is nothing needed to be returned
{
	for (int i = last_nr; i >= first_nr; i--){	//goes through everynumber starting with the "last_nr" and ends with the "start_nr"
		for (int j = i-1; j >= 2; j--){			//divides the current number by everynumber between 2 and the current number - 1
			if ((i%j) == 0){					//if it is divided and has a remander of 0
				isPrime = false;				//it is not prime
			}
		}
		if (isPrime == false){					//if it is not prime
			isPrime = true;						//reset bool value
		}else{									//if it is true
			cout << i << endl;					//print out the number
		}
	}
}

// Main function
int main()
{
	do
	{
		field();

		prime();

		cout << "Fill in another field of numbers (y/n)?" << endl;
		cin >> close;
	}
	while (close == 'y' || close == 'Y');	//translation miss =)
	return 0;
}

next thing to do is try and get rid of the goto statements, they are bad practice, but this worked for me =)

[tition]

ummm... what you did is fine but it's not Eratosthenes' method (this dude was one of the ancient Greeks, cheers to the southern neighbors!).

To do Eratosthenes' method you must do smth along the lines of:

bool Visited[10000];
for (int i=0;i<10000;i++)
{ Visited[i]=false;
}
int step=2;

while(step<10000)
{ if (!Visited[step-1])
  { for (int j=2*step;j<10000;j+=step)
    { Visited[j-1]=true;
    }
  }
  step++;
}
//now all indices i for which Visited[i] is false will be prime!
for (int i=0; i<10000;i++)
{ if (Visited[i])
  { std::cout>> i>>"\n";
  }
}

[wmheric]

yes I thought of an array of size of how many numbers are in the range (initialize the size at runtime if you can, but luckily they are just Booleans)
but I wonder if the you can start the sieve of Eratosthenes with an arbitary number, so no matter what the user input as the lower bound, you have to "sieve" from 2, unless you find some way to "pre-sieve"

[mcleano]

On a different aspect of your program, you need to change the use of goto: this is bad programming in c++!

You can use control structures instead: http://www.cplusplus.com/doc/tutorial/control/

[jsmith]

Sieve of Eratosthenes requires that the algorithm start at 2. What you store in the array is another story.
You must "scratch off" all the multiples that are within the range you are storing.

[Splinter007]

Hey everyone, thanks for your replies!

To kartracer12: Thanks for the code, works great!
To mcleano: I actually found goto on accident, I was looking for a way to sort of 'restart' the program if one of the errors occured, and in a blaze of randomness I typed in goto and it seemed to work, but thanks for the tip anyway!

Greets

[z05DSL3A]

#include <iostream>

/******************************************************************************
The sieve of Eratosthenes to determine prime numbers
The algorithm
1 Create a contiguous list of numbers from two to some integer n.
2 Strike out from the list all multiples of two (4, 6, 8 etc.).
3 The list's next number that has not been struck out is a prime number.
4 Strike out from the list all multiples of the number you identified in the 
  previous step.
5 Repeat steps 3 and 4 until you reach n.
******************************************************************************/
long sieve(long n, long* primes) 
{
    if (n<2) return 0; 
    
    const char blank = 0;
    const char marked = 1;

    char* theSieve;

    theSieve = new char[n+1];
    
    for (long k=2; k<=n; k++) 
        theSieve[k] = blank;

    long idx = 0;
  
    for (long k=2; k<=n; k++) 
    {
        if (theSieve[k]==blank) 
        {
            theSieve[k] = marked;
            primes[idx] = k;
            idx++;

            for(long d=2*k; d<=n; d+=k) 
                theSieve[d] = marked;
        }
    }
    delete[] theSieve;
    return idx;
}

//-----------------------------------------------------------------------------

const long N = 10000000;
const long TABLE_SIZE = 800000;

int main() 
{
    long* primes; 
    primes = new long[TABLE_SIZE];
    long np = sieve(N,primes);

    std::cout << "Found " << np << " prime numbers" << std::endl;
    std::cout << "The largest prime number is " << primes[np-1] << std::endl;

    delete[] primes;

    return 0;
}