I need to get all the prime numbers from 1 to a large number?

Question

I need to create a program that can get all the prime numbers from 1 to a large number. I have a getPrime method which returns true if the number is prime or false if it is not prime. When I use this method and a while loop to get a list of prime numbers from 1 to a large number it keeps returning 24 then 4 then 5.the variable end, in code below is asked for in a prime class runner separately. Here is my code:

public class Prime 
{

    private long userNumber;
    private int numRoot;
    private int x;
    private boolean isPrime;
    private int factors;
    private long end;
    private int i;

    public void setUserNumber(long num)
    { 
       userNumber = num;
    }

    public void setEndNumber(long n)
    { 
        end = n;
    }

    public boolean getPrime()
    {
        numRoot = ((int)Math.sqrt(userNumber));


        for (x=2; x<=numRoot; x++)
        {
            if ((userNumber % x) == 0)
            {
                factors++;        
            }
        }

        if (factors >1) {
            isPrime = false;
        }
        else {
            isPrime = true;
        }
        return  isPrime;
    }  
    public void getPrimeList()
    {
        if(end < 2) {
            System.out.println("No prime numbers");
            System.exit(0);
        }
        System.out.printf("\nThe prime numbers from 1 to %d are: \n 2", end);
        Prime primeNum = new Prime();
        i = 3;
        while( i <= end )
        {
            userNumber = i;
            getPrime();
            if (isPrime == true)
            {
                System.out.println(userNumber);
            }
            i++;
        }
        System.out.println();
    }
 }

Answer 1

public void getPrimes(int N) {
    for (int i = 2; i <= N; i++) {
        if (isPrime(i)) System.out.println(i);
    }
    System.out.println("These are all the prime numbers less than or equal to N.");
}

private boolean isPrime(int N) {
    if (N < 2) return false;
    for (int i = 2; i <= Math.sqrt(N); i++) {
        if (N % i == 0) return false;
    }
    return true;
}

Answer 2

The code below is written in C#, although it will work in Java with very little modification. I use a long as the data type as you haven't been specific when you say "a large number".

    public static bool isPrime(long Number)
    {
        if (Number == 1) { return false; }
        int i = 2;
        while (i < Number)
        {
            if (Number % i++ == 0) { return false; }
        }
        return true;
    }

It can be applied like so, again this is C#, but will work in Java with little modification.

    while (i <= LARGE_NUMBER)
    {
        Console.Write((isPrime(i) ? i.ToString() + "\n" : ""));
        i++;
    }

Answer 3

public class PrimeTest{
    private static final int MAX_NUM = Integer.MAX_VALUE; // your big number

    public static void main(String[] args) {
        int count = 0;
        for(int i=0; i<MAX_NUM; i++) {
            if (isPrime(i)) {
                System.out.printf("Prime number %d\n", i);
                count++;
            }
        }
        System.out.printf("There is %d prime numbers between %d and %d\n", count, 0, MAX_NUM);
    }


    public static boolean isPrime(int number) {
        if (number < 2) {
            return false;
        }
        for (int i=2; i*i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 4

A prime number p should have zero factors between 2 and sqrt(p), but you are allowing one here:

if (factors >1){
    isPrime = false;
}

In fact, there's no need to count factors at all, you can directly do

if ((userNumber % x) == 0) {
    return false; 
}

If you however need to count factors anyways, I would suggest setting factors explicitly to 0 at the start. It's not a good practice to rely on implicit initial values.

Answer 5

The problem is that you're using too many instance variables inside getPrime, causing you to unintentionally inherit state from previous iterations. More precisely, factors should be reset to 0 at the start of getPrime.

A better way to go about this is by making x, numRoot, isPrime and factors local variables of getPrime:

public boolean getPrime()
{
    int factors = 0;
    boolean isPrime;
    int numRoot = ((int) Math.sqrt(userNumber));

    for (int x=2; x<=numRoot; x++)
    {
        if ((userNumber % x) == 0)
        {
            factors++;        
        }
    }

    if (factors >1){
        isPrime = false;
    } else {
        isPrime = true;
    }
    return  isPrime;
}

You can go even further and make userNumber an argument of getPrime:

    public boolean getPrime(int userNumber)
    {
        // ...

and call it with:

while( i <= end )
{
            isPrime = getPrime(i);
    if (isPrime)
    {
        System.out.println(userNumber);
    }
    i++;
}

Two things to note:

• I removed the usage of userNumber inside getPrimeList completely, I simply use i instead.
• The isPrime could be removed as well if it's not needed elsewhere, simply use if(getPrime(i)) { ... } instead.

Answer 6

Your algorithm is the wrong solution for your task. The task is to find all primes from 2 to N, the appropriate algorithm is the Sieve of Eratosthenes. (See here for an epic rant discussing basics and optimizations of sieve algorithms.)

It is known that all primes are either 2,3,5,7,11,13 or of the form

30*k-13, 30*k-11, 30*k-7, 30*k-1, 30*k+1, 30*k+7, 30*k+11, 30*k+13,

for k=1,2,3,...

So you generate an array boolean isPrime[N+1], set all to true and for any candidate prime p of the form above, until pp>N and if isPrime[p] is true, set all isPrime[kp]=false for k=2,3,4,...N/p.

---

int N;
Boolean isPrime[] = new Boolean[N+6];

static void cross_out(int p) {
    for(int k=5*p, d=2; k<N; k+=d*p, d=6-d) {
         isPrime[k]=false;
    }
}

static void sieve() {
    for(int k=0; k<N; k+=6) {
        isPrime[k  ]=isPrime[k+2]=false;
        isPrime[k+3]=isPrime[k+4]=false;
        isPrime[k+1]=isPrime[k+5]=true;
    }
    for(int k=5, d=2; k*k<N; k+=d; d=6-d) {
        if(isPrime[k]) cross_out(k);
    }
}