# Prime Numbers

• 04-29-2002
cmangel518
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 :confused: 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!!!!! :D

Christina
• 04-29-2002
Barjor
Your idea sounds about right. Try to build some code around it or search the board. It have been answeared many times before.
• 04-29-2002
Davros
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?
• 04-29-2002
cmangel518
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?
• 04-29-2002
ygfperson
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.
• 04-29-2002
Davros
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?
• 04-29-2002
fyodor
Technically, 1 is not prime.
• 04-29-2002
itld
howdy,
ive been out of school for a long time BUT this
Quote:

although I think someone recently suggested an order 25 polynomial equation.
seems a bit extreme to me.

itld reaches for college calculus book.

M.R.
• 04-30-2002
Davros
> 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.
• 04-30-2002
Will
Ok. I don't know if you just want the code, or if you want to do it yourself. If you want the code, look down, if you want to figure it out yourself, look up the Sieve of Eratosthenes.

Code:

```#include <iostream.h> #define arraysize 30  //defining makes code more readable than just putting a sentinal in void main() {         int primes[arraysize]={1}; //#1 is set to 1, everything else is still 0         int pause=0;  //garbage variable, used to stop the text from                                 //scrolling for a moment.         for (int i = 2; i <= arraysize/2; i++)         {                 for (int j = 2; (j * i) < arraysize; j++)                 {                 primes[j * i] = 1; //all non-primes are set to one                 }         }         for (i = 1; i < arraysize; i++)         {                 if (primes[i] == 0)             cout<< i << " is a prime number." << endl;                 if ((i % 50) == 0)                 {                         cout << "Enter any number to continue."<<endl;                         cin >> pause;                 }         } }```
• 04-30-2002
cmangel518
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])
}

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 :D!!! LOL

• 04-30-2002
Leeman_s
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?
• 04-30-2002
ss3x
i do believe this is where the mod math function should be used :)
• 04-30-2002
Liam Battle
if you want to estimate a set of numbers you can simply use the mathematical formula by Bernoulli,
if you use the formula :

z
__ = B0 + B1^z + B2z^2 Bkz^k
-------- + ... = E ---------
e^z -1 2! k>0 k!

that will get you an approximation based on a set of numbers, just apply that formula to your algorithm..

or you can use Eulers General Formula.

if anyone else goes to stamford they will know what im talking about...

if not sorry...

ugh i just looked at the post and it formated the formula wrong on the screen... sorry