CODEWITHSUNDEEP
javaprimes
maclunian
maclunian

Reputation: 8023

Is there a more efficient way to write the following Prime Number code?

I have the following code which spits out prime numbers between 1 and N. A friend came up with this solution but I believe there is a more efficient way to write this code. Such as making it so that if (i%j!=0) {System.out.print (i + " ");}. However I found this spat out numbers randomly all over the place...

import java.util.Scanner;

public class AllPrime {


public static void main(String[] args) {

    System.out.println("Enter a number:\n");
    Scanner input = new Scanner(System.in);
    int a = input.nextInt();

    for (int i = 2; i < a; i++) {
        boolean primeNum = true;
        for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }
        if (primeNum) {
            System.out.print(i + " ");
            }
        }
    }
}

Upvotes: 1

Views: 2133

Answers (4)

user unknown
user unknown

Reputation: 36269

public static boolean [] createPrimes (final int MAX)
{
         boolean [] primes = new boolean [MAX];
         // Make only odd numbers kandidates...
         for (int i = 3; i < MAX; i+=2)
         {
                primes[i] = true;
         }
         // ... except No. 2
         primes[2] = true;

         for (int i = 3; i < MAX; i+=2)
         {
                /*
If a number z is already eliminated
(like No. 9), because it is a multiple of - 
for example 3, then all multiples of z 
are already eliminated.
                */
                if (primes[i] && i < MAX/i)
                {
                        int j = i * i;
                        while (j < MAX)
                        {
                                if (primes[j])
                                        primes[j] = false;
                                j+=2*i;
                        }
                }
        }
        return primes;
}

updated after comment of Will Ness:

Improves the speed to about 2/1, it checks 100 Million ints in 5s on my 2Ghz single core.

Upvotes: 1

Sathwick
Sathwick

Reputation: 1331

private static void generatePrimes(int maxNum) {

    boolean[] isPrime = new boolean[maxNum + 1];
    for (int i = 2; i <= maxNum; i++)
        isPrime[i] = true;

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i * i <= Math.sqrt(maxNum); i++) {

    // if i is prime, then mark multiples of i as nonprime
    if (isPrime[i]) {
        for (int j = i; i * j <= maxNum; j++)
        isPrime[i * j] = false;
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= maxNum; i++)
        if (isPrime[i]) {
        System.out.println("Prime - " + i);
        primes++;
        }
            System.out.println("The number of primes <= " + maxNum + " is "+ primes);
    }

Upvotes: -1

Thilo
Thilo

Reputation: 262850

for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }

This is not a very efficient algorithm, but at the very least, put a break in there...

Upvotes: 1

Federico Lebr&#243;n
Federico Lebr&#243;n

Reputation: 1802

Look at proper sieves, like the Sieve of Eratosthenes. You don't need to be checking for % each time.

Upvotes: 4

Related Questions