Finding Primes With An Array

Question

I have the following program that prints the prime numbers from 1 to 100 with loops. How could I store the values of those primes in an array and print them out from that array? I tried initializing int[] n =1 but it didn't like that at all. Thanks guys!!!

public class PrimeGenerator 
{
  public static void main(String[] args) 
  {
    int max = 100;

    System.out.println("Generate Prime numbers between 1 and 100. \"1\" is not prime.");

    // loop through the numbers one by one
    for (int n = 1; n<max; n++) {
      boolean prime = true;
      //analyzes if n is prime      

      for (int j = 2; j < n; j++) {
        if (n % j == 0 ) {
          prime = false;
          break; // exit the inner for loop
        }
      }

      //outputs primes
      if (prime && n != 1) {    
        System.out.print(n + " ");
      }
    }
  }
}

Use a `List` instead of an array since you don't know how many primes there will be. — m0skit0, Nov 16 '13 at 17:59
possible duplicate of [How to find prime numbers between 0 - 100?](http://stackoverflow.com/questions/11966520/how-to-find-prime-numbers-between-0-100) — Thomas Ahle, Jun 12 '14 at 13:19

Akira · Accepted Answer · 2013-11-16T18:14:07.040

1

Simply use an ArrayList to store all primes found.

import java.util.ArrayList;

public class PrimeGenerator {
    public static void main(String[] args) {
        int max = 100;

        System.out.println("Generate Prime numbers between 1 and 100. \"1\" is not prime.");

        ArrayList<Integer> list = new ArrayList<Integer>();

        // loop through the numbers one by one
        for (int n = 1; n < max; n++) {
            boolean prime = true;
            // analyzes if n is prime

            for (int j = 2; j < n; j++) {
                if (n % j == 0) {
                    prime = false;
                    break; // exit the inner for loop
                    }
            }
            if (prime && n != 1) {
                list.add(n);
            }
        }
        for (int i : list) {
            System.out.println(i + " ");
        }
    }
}

edited Nov 16 '13 at 18:14

answered Nov 16 '13 at 18:00

Akira

4,001
1
16
24

Oh! Where would I initialize it? In the for loop? – Lou44 Nov 16 '13 at 18:01
You forgot to start for-loop with `n=2` – agbinfo Nov 16 '13 at 18:06
My solution assumes you want to do something with the prime numbers other than simply printing them on System.out. If you want to throw them away, then instead of adding to the list, simply print them. Also, you do not need to check j until n. You can stop if you reach the square root of n. – Akira Nov 16 '13 at 18:10

score 0 · Answer 2 · answered Nov 16 '13 at 18:03

try this

int max = 100;

    System.out.println("Generate Prime numbers between 1 and 100. \"1\" is not prime.");
    ArrayList<Integer> primenumbers = new ArrayList<>();
    // loop through the numbers one by one
    for (int n = 1; n < max; n++) {
        boolean prime = true;
        // analyzes if n is prime

        for (int j = 2; j < n; j++) {
            if (n % j == 0) {
                prime = false;
                break; // exit the inner for loop
            }

        }

        // outputs primes
        if (prime && n != 1) {

            primenumbers.add(n);

        }
    }
    System.out.println(primenumbers);

The last line should be `System.out.println(Arrays.toString(primenumbers))` because `primenumbers` is an Object. — RouteMapper, Nov 16 '13 at 18:05

score 0 · Answer 3 · answered Nov 16 '13 at 18:18

An efficient prime finder is the 'Sieve of Atkin' and I have this stored for most of the problems on 'Project Euler' than involve primes. It can compute on my machine up to 1 billion (in under a minute) and print them out.

import java.util.Arrays;

public class SieveOfAtkin {
private static int limit = 1000000;
private static boolean[] sieve = new boolean[limit + 1];
private static int limitSqrt = (int)Math.sqrt((double)limit);

public static void main(String[] args) {
    // there may be more efficient data structure
    // arrangements than this (there are!) but
    // this is the algorithm in Wikipedia
    // initialize results array
    Arrays.fill(sieve, false);
    // the sieve works only for integers > 3, so 
    // set these trivially to their proper values
    sieve[0] = false;
    sieve[1] = false;
    sieve[2] = true;
    sieve[3] = true;

    // loop through all possible integer values for x and y
    // up to the square root of the max prime for the sieve
    // we don't need any larger values for x or y since the
    // max value for x or y will be the square root of n
    // in the quadratics
    // the theorem showed that the quadratics will produce all
    // primes that also satisfy their wheel factorizations, so
    // we can produce the value of n from the quadratic first
    // and then filter n through the wheel quadratic 
    // there may be more efficient ways to do this, but this
    // is the design in the Wikipedia article
    // loop through all integers for x and y for calculating
    // the quadratics
    for (int x = 1; x <= limitSqrt; x++) {
        for (int y = 1; y <= limitSqrt; y++) {
            // first quadratic using m = 12 and r in R1 = {r : 1, 5}
            int n = (4 * x * x) + (y * y);
            if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
                sieve[n] = !sieve[n];
            }
            // second quadratic using m = 12 and r in R2 = {r : 7}
            n = (3 * x * x) + (y * y);
            if (n <= limit && (n % 12 == 7)) {
                sieve[n] = !sieve[n];
            }
            // third quadratic using m = 12 and r in R3 = {r : 11}
            n = (3 * x * x) - (y * y);
            if (x > y && n <= limit && (n % 12 == 11)) {
                sieve[n] = !sieve[n];
            } // end if
            // note that R1 union R2 union R3 is the set R
            // R = {r : 1, 5, 7, 11}
            // which is all values 0 < r < 12 where r is 
            // a relative prime of 12
            // Thus all primes become candidates
        } // end for
    } // end for
    // remove all perfect squares since the quadratic
    // wheel factorization filter removes only some of them
    for (int n = 5; n <= limitSqrt; n++) {
        if (sieve[n]) {
            int x = n * n;
            for (int i = x; i <= limit; i += x) {
                sieve[i] = false;
            } // end for
        } // end if
    } // end for
    // put the results to the System.out device
    // in 10x10 blocks

    for( int i = 0 ; i < sieve.length ; i ++ ) {
        if(sieve[i])
            System.out.println(i);
    }
} // end main
} // end class SieveOfAtkin

Finding Primes With An Array

3 Answers3