CODEWITHSUNDEEP
javamethodsprimes
CBH
CBH

Reputation: 95

Printing out Prime Numbers from 2 to 1000

I am writing a code that write all the prime numbers from 2 to 1000 in a file, named primes.txt. For some reason I am not able to figure out the correct way to do this problem. 

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;

public class Problem6 {

    /**
     * @param args
     * @throws FileNotFoundException 
     */
    public static void main(String[] args) throws FileNotFoundException {
        PrintWriter prw = new PrintWriter("primes.txt");
        for (int i = 2; i <= 1000; i++){
            if (checkIfPrime(i) == true){
                System.out.println(i);
                prw.println(i);
            }
        }
    }

    public static boolean checkIfPrime (int num){
        boolean isPrime = true;  
        for (int i = 2; i <= 1000; i++){
            if ( num % i == 0 ){
                isPrime = false;
            }
        }

        return isPrime;
    }
}

I just dont know what to do... Please help Thanks!

Upvotes: 1

Views: 9732

Answers (5)

Will Ness
Will Ness

Reputation: 71099

Here's how you could "hard-code" an incremental sieve of Eratosthenes on a 2-3-5-7 wheel to print the primes up to 1000. In C-like pseudocode,

primes_1000()
{
   // the 2-3-5-7 wheel
   int wh[48] = {10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,
                  2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2};
   // core primes' multiples, each with its pointer into the wheel
   int m[7][4] = { {1,11,11,11*11}, {2,13,13,13*13}, {3,17,17,17*17},
                   {4,19,19,19*19}, {5,23,23,23*23}, {6,29,29,29*29},
                   {7,31,31,31*31} };    // 23*23 = 529 
   int i=1, p=11, k=0;
   print(2); print(3); print(5); print(7);
   p = 11;             // first number on the wheel - the first candidate
   do {
      // the smallest duplicate multiple is 121*13, ==> no dups below 1000!
      for( k=0; k < 7; ++k) {
         if ( p == m[k][3] ) {             // p is a multiple of m[k][1] prime:
            m[k][2] += wh[ m[k][0]++ ];    //   next number on the wheel
            m[k][3]  = m[k][1] * m[k][2];  //   next multiple of m[k][1] 
            m[k][0] %= 48;                 //   index into the wheel
            break;
         }
      }
      if (k == 7) {    // multiple of no prime below 32 -
          print(p);    //   - a prime below 1000!   (32^2 = 1024)
      }
      p += wh[i++];    // next number on the candidates wheel
      i %= 48;         // wrap around to simulate circular list
   } while ( p < 1000 );
}

For primes below 500, only 4 sieve variables need to be maintained, for the additional core primes {11,13,17,19} above the wheel's inherent primes 2,3,5,7.

(see also Printing prime numbers from 1 through 100).

m is the dictionary of base primes and their multiples on the wheel (multiplesOf(p) = map( multiplyBy(p), rollWheelFrom(p) ), each with its own index into the wheel. It should really be a priority queue, min-ordered by the multiples' values.

For a true unbounded solution a separate primes supply can be maintained, to extend the dictionary prime by prime when the next prime's square is reached among the candidates.

Upvotes: 0

Braj Kishore
Braj Kishore

Reputation: 351

calculation can be made even faster by checking the division with prime numbers only. Any non prime number is divisible by some prime number smaller than itself. 

    static List<Integer> primes = new ArrayList<Integer>();

public static void main(String[] args) {
    for (int i = 2; i < 10000; i++) {
        if(checkPrime(i)){
            primes.add(i);
        }
    }
    System.out.println(primes);
}

private static boolean checkPrime(int n) {
    for (Integer i : primes) {
        if(i*i > n ){
            break;
        }else if(n%i==0 )
            return false;
     }
    return true;
}

Upvotes: 3

Pshemo
Pshemo

Reputation: 124265

Change your for condition in checkIfPrime(int num) to 

for (int i = 2; i < num; i++) {

BTW if (checkIfPrime(i) == true){ can be written as if (checkIfPrime(i)){

Upvotes: 2

rgettman
rgettman

Reputation: 178303

What happens when you pass in your first number, 2, to checkIfPrime? It will take remainder of 2 divided by 2, which is 0, falsely claiming that 2 is not prime.

You need to stop testing remainders before you actually get to num. Stop your i for loop before i gets to num. (In fact, you can stop after i has reached the square root of num).

for (int i = 2; i < num; i++){

or even

for (int i = 2; i <= Math.sqrt(num); i++){

If you're feeling adventurous, you may try implementing the Sieve of Eratosthenes, which marks all composite numbers up to an arbitrary limit (in this question, 1000). Then you just print out the rest of the numbers -- the primes.

Upvotes: 6

nickie
nickie

Reputation: 5818

A number num is prime if it's not divisible by any other number that is greater than one and smaller than num. Where is this in your code? :-)

Upvotes: 1

Related Questions