[Phantom_of_the_opera]

1

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:38 AM

[skyhawk133]

Someone didn't read the instructions:

Quote

I have done the following before posting a new topic:
- Searched for my problem using the search box on the right
- Given my thread a descriptive title (Not "Help", "Homework Problem", etc.)
- Put [code]code here[ /code] tags around my code
- Included any errors and a description of my problem

[NickDMax]

Well there are a few ways to calculate prime numbers. Most of them a sieve method, meaning that we take out the numbers which are NOT prime. For example: Take an array of numbers from 2 to 100, starting with 2, remove all other multiples of 2 (setting the array elements to zero). then look for the next non-zero number (in this case 3) and take out all multiples of 3.

Now our array looks like {2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13...} now we find the next nonzero member {5} and take out all multiples of 5.

This method stated as such would not be much help calculating the first 100000 prime numbers as you wuold need an array capable of holding all of the numbers (about 1318699 elements) but it is the idea. This is called the sieve or Eratosthenes and the link there provides some pseudocode examples.

Another popular begining method is to make an "isPrime(int n)" which checks all numbers from n to sqrt n to see if any of those divide the numbers.... a note though, if you are using a table to store calculated prime numbers then you can use this table to vastly reduce the number of checks by using the primes already calculated.

I have seen about 100 different methods think about prime numbers and thier properties and work out your own. That way you understand exatly how it works.

This post has been edited by NickDMax: 22 March 2007 - 01:28 PM

[Phantom_of_the_opera]

.

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:38 AM

[born2c0de]

Quote

Well I now realize that you cannot pass an Array as a reference, my mistake

You made no mistake.
Arrays are passed by reference.
The address of the first element is always passed.

[NickDMax]

well you can pass arrays to functions

void foo(int *a);
...
int array[10];
foo(array);
cout << a[0] << a[1];

void foo(int *a)
{
	a[0]=1;
	a[1]=2;
	return;
}

so you can pass the same array to Calculate and to Print.

[Phantom_of_the_opera]

.

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:39 AM

[Phantom_of_the_opera]

.

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:39 AM

[NickDMax]

well first off as I read it, the assignment said to calculate the "first n prime numbers" and you program would calculate all prime numbers up to n. There is a big differance. The 1000'th prime is 7919, where as the largest prime less than 1000 is 997 which is the 168'th prime... so your program would calculate far less then n primes.

so how might this work. Well suppose we take a differnent aproch. We make an array of known primes (int arePrime[100000]) and we poplulate it with primes as we find them. In our loop to prove a number prime we only need to check to see is (num % divisor) == 0 as long as divisor is a prime number (and what do you know we are making an array of them, maybe we can use the ones we already know to find the next one...)

So we have an array (arePrime[]) containing all the prime numbers we know... well we will need a variable (numPrimes) to tell us how many we have found so far.

Now we can define a function to find the next prime number, passing it the array of known numbers, and a pointer to the number of known primes in that array.

inside the function we initialize the number we want to check to the last known prime number +1, then we loop though all known primes and see if (number % arePrime[i] == 0) if so, this is not a prime, if we get though all known primes it IS a prime and can be added to the array.

pseudocode:

int findNextPrime(int[] arePrime, int numPrimes)
{
	int curNumber <-- arePrime[numPrimes - 1]
	while (no prime found && curNumber < Maximum int value)
	{
		curNumber++ 
		for(int i=0; i<numPrimes; i++)
		{
			if (curNumber % arePrime[i] == 0) 
			{
				not a prime
				break
			 }
		 }
	}
	if (found prime) return curNumber 
	else return 0;
}

With this algorithm you could calculate as many primes as your array could hold (you would have to initalize the array with 2) as long as the n'th prime is not greater than the int size. There are a few improvements that I can think of to make it run faster for larger values of n, but it is better than checking all odds up to sqrt(curNumber) by far as is.

[Phantom_of_the_opera]

.

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:39 AM

[Phantom_of_the_opera]

.

This post has been edited by Phantom_of_the_opera: 03 May 2007 - 11:39 AM

[Amadeus]

You do not appear to have a function named print? Is the post above missing some code?

[Phantom_of_the_opera]

the post above that has it in there, that's what I have for it anyways... I haven't made any improvements on it yet, still trying to get it to work.