# Prime number program



## jacy (Jul 19, 2004)

Hello everyone,
I have written a prime number program. It works fine and gives me the desired result, but i would like to know if i could write it in a better way thanks.


```
#include<iostream>
using namespace std;
int main ()
{
    int prime_no;
    int number=1;
    cout<<"Enter a number : ";
    cin >> prime_no;
    
    if (prime_no==1 || prime_no==2)
      {
      cout<<" The number is prime\n";
      }
     else
     if (prime_no%2==0)                   // if it is even number, then its not prime.
     {
      cout<<"The number is not prime\n";
      }
      
         else
         if (prime_no%3==0)              // if divisible by 3, then its not a prime number.
         {
          cout<<"The number is not prime\n";
          
          }
            else
            if (prime_no%5==0)            // divisible by 5 then not a prime.   
             {
              cout<<"The number is not prime\n";
             }
               else
               if (prime_no%7==0)          // divisible by 7 then not a prime.
               {
                cout<<"The number is not prime\n";
               }
          else
          {
              cout<<"The number is prime\n";  //If not divisble by 3,5,or 7 then its a prime number.  
          }
           
        
  system("pause");
  return 0;
}
```


----------



## chatterjee (Jul 12, 2005)

I don't know C language but I did a similar program in QBASIC.Look at the following code,it's easily comprehensible:

n1=INT(n/2)
FOR i= 2 TO n1
R= n mod i
IF R=0 THEN PRINT "IT'S NOT PRIME" ELSE PRINT "IT'S PRIME"
NEXT i


----------



## bpmurray (Jun 3, 2003)

Probably the most famous mechanism is the Sieve of Eratosthenes. This involves filling an array with flags indicating whether it's interesting or not. Initially, the array is set to "all interesting", and the entries are progressively set to "not interesting" as factors of the current number are set. Eventually, you end up with a set of flags at the prime numbers. 

The limitation of this is that you need to allocate an array the same size as the maximum, so you're restricted by how much memory you can grab, probably of the order of 10s of millions. However, it is very fast, much faster than the brute force mechanism here.


----------



## Chicon (Jul 29, 2004)

Hi chatterjee,

In your example, the limit *n1* can be set to *INT(SQRT)* .


----------



## GCDude (Apr 1, 2005)

Also have a search on "Miller-Rabin primality test"

http://en.wikipedia.org/wiki/Miller-Rabin_primality_test


----------



## chatterjee (Jul 12, 2005)

Chicon said:


> n your example, the limit n1 can be set to INT(SQRT)


Why?


----------



## Chicon (Jul 29, 2004)

chatterjee said:


> Why?


Because, if you find a divisor after the square root limit, that means you already have found a divisor smaller than the square root.
Logical ? 


```
[SIZE=3][B]

If (N = A * B) and (A=B) then A = SQRT(N) or B = SQRT(N)

If (N = A * B) and (A<B) then A < SQRT(N) and B > SQRT(N)

Example :

12 = 3 * 4 then 3 < SQRT(12) and 4 > SQRT(12)

SQRT(12) = 3.4146....
[/B][/SIZE]
```


----------



## kidnewbie (Mar 8, 2006)

```
#include <iostream.h>

int main()
{
    while (true)
    {
        int num = 0;
        int prime = 1;
        cout << "Enter a number:  ";
        cin >> num;
        for (int i = 1; i <= num; i++)
        {
           if ((i != 1) && (i != num) && (num % i == 0)) {prime = 0;} 
        }
        if (prime == 1)
        {
            cout << "Number is prime.\n\n";
        }    
        else
        {
            cout << "Number is composite.\n\n";
        }
    }
    system("PAUSE");
    return 0;
}
```
i also have it in an infinite loop so you could test as many numbers as you want. it should work for any number but it will run slow prime number is greater than maybe 999999991


----------



## blaqDeaph (Nov 22, 2005)

Basically, since the number of primes are unlimited, you'd be wanting to test primes within a range, Usually like finding the first 10k primes etc.

To do that, personally the sieve technique has always worked for me. It just requires some optimization on the part of memory useage. Since all you really need is an array of bits, you should have more than enough space to calculate the first few million primes on even an average computer.


----------



## Chicon (Jul 29, 2004)

Here, I've attached a java source using an array of integers. The program computes the first 1000 prime numbers. I tested it and it took 1 second to display the results. 


```
[SIZE=3][B]
/*
 * Main.java
 *
 * Created on 11 mars 2006, 10:18
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package test;

/**
 *
 * @author Chicon
 */
public class Main {
    
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int[] res = PrimeNumber(1000);
        for (int i = 0; i < 1000; i++) {
            System.out.println(res[i]);
        }
    }
    
    public static int[] PrimeNumber(int n) {  // This method returns an array
                                              // of n first prime numbers
        int[] pn = new int[n];                // initialization of the array
        pn[0] = 1;                            // The 2 first prime numbers are
        pn[1] = 2;                            // already stored in the array
        int i;                                // increment of the main loop
        int j;                                // increment of the inner loop
        boolean isPrimeNumber;                // true if the test number is prime
        boolean existDivisor;                 // true if a divisor exists and false otherwise
        int test_number = 3;                  // the number to test is set to 3
        int rem;                              // the remainder of the division
    
        for (i = 2; i < n; i++) {             // Main loop
            isPrimeNumber = false;
            while (!isPrimeNumber) {          // Loop until a prime number is found
                existDivisor = false;
                j = 1;
                while ((!existDivisor) && (j < i)) {
                    rem = test_number % pn[j];
                    if (rem == 0) {
                        existDivisor = true;
                    }
                    else {
                       j++;
                    }
                }
                if (existDivisor) {
                    test_number++;
                }
                else {
                    isPrimeNumber = true;
                }
            }
            pn[i] = test_number;              // store the prime number in the array
            test_number++;
        }
        return pn;                     // return of the array  
    }    
}

[/B][/SIZE]
```


----------



## aewarnick (Sep 3, 2002)

for(;
is faster than
while(true)

because there is no check every loop.


----------



## blaqDeaph (Nov 22, 2005)

aewarnick said:


> for(;
> is faster than
> while(true)
> 
> because there is no check every loop.


Isn't there still a check to see if the condition has been met? And since true is just a value there isnt much checking to do.


----------



## aewarnick (Sep 3, 2002)

No. If you compare the asm code of while(true) and for(;, they are not the same, and they shouldn't be. for(; has no bounds check.


----------

