Thread: Prime Numbers

I'm not really sure how to phrase this, so please bear with me. I need to write a program, that amongst other things, uses an "equation" (not just spitting out "1, 2, 3, 5....") to display 30 prime numbers. I don't want to "cheat" like I'm seeing some other students doing, but I'm not sure where to start. If anyone has any ideas on how to do this or where to look, I'd really appreciate it.
The only thing I can think of doing so far is testing a heck of alot of numbers by dividing by the numbers 2-11 with/without a remainder (as long as the divisor isn't the one I'm using to test), but if I do that I'm not sure how to set up the loop to display 30 numbers and just not test 30 numbers. I hope this makes sense, and ANY help/examples anyone could provide would be helpful!!!!!

Christina

Your idea sounds about right. Try to build some code around it or search the board. It have been answeared many times before.

Technically speaking, there is no known (at least accepted) equation for spitting out prime numbers, although I think someone recently suggested an order 25 polynomial equation.

Are you talking about an equation, or an algorithm?

It was phrased "equation" only to prevent us from just spitting out what we already know without allowing the program to do the work...does that clear it up?

so, in other words, the program find prime numbers in any way, but it cannot just have

Code:

printf("2, 3, 5, etc...");

it must figure it out?
like Barjor said, it's been answered many times before. try a brute force method. or the sieve of erethosenese... whatever that spelling was.

Then its an algorithm. (I was't being pedantic)

I suggest that you create a function to fill out an array of 30 integers - your prime number results.

Your function should run around a loop incrementing a count by two each time, starting from one (i.e. so you only get odd numbers*).

For each count (n), you should run through divisor tests from 3 to the square root of n (there's no point in testing divisors above the square root). If no test divisor fits into n without a remainder, add n to your result array and continue the increment until you fill all 30 elements.

* The values 1 & 2 may be considered prime numbers, but because these are exceptions, I would reckon it would be acceptable to hard code these as results if required.

When your function returns, output the results to screen.

Question? Is your algorithm really a true algorithm? I.e. can we prove that it will return in a finite time?

Technically, 1 is not prime.

> seems a bit extreme to me.

Well, it depends on what you want to do. Generating a lot of prime numbers quickly is important if you want to break an RSA algorithm. The problem with generate & test algorithms is that they get progressively slower the larger the number. This is one of the reasons why prime numbers are so important in encryption.

If you could have an equation that looked like this:

a = f(n)

where a is always prime. That would be quite a break through.

Well, if I had done a more thorough search in Borland's help, I would have been all set. This is what I came up with...

{
RichEdit1->Lines->Insert(0,1);
const int sievesize = 125;
vector<int,allocator<int> > sieve(sievesize, 1);

for (int i = 2; i * i < sievesize; i++)
if (sieve[i])
for (int j = i + i; j < sievesize; j += i)
sieve[j] = 0;

for (int j = 2; j < sievesize; j++)
if (sieve[j])
RichEdit1->Lines->Add(j++);
}

Now I just need to be a bit more intellegent to get this to sort in descending order...oh boy.

For now I'll move on to writing the code for the Fibonacci Sequence.

Just one more week of this and I'll be done !!! LOL

Thanks for your help!!

Code:

#include "iostream.h"
#include "iomanip.h"

int main()
{
	const int MAX=100;
	long primes[MAX]={2,3,5};
	long trial=5;
	int count=3;
	int found=0;


	do
	{
		trial+=2;
		found=0;
		for(int i=0;i<count;i++)
		{
			found=(trial % *(primes + i)) == 0;

			if(found)
				break;
		}
		if (found==0)
			*(primes + count++) = trial;
	}while(count<MAX);

	for(int i = 0;i < MAX;i++)
	{
		if(i % 5 == 0)
			cout<<endl;
		cout<<setw(10)<<*(primes + i);
	}
	cout<<endl;
	return 0;
}

hows that?