Java 用数组寻找素数

Finding Primes With An Array

提问by Lou44

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!!!

我有以下程序可以循环打印从 1 到 100 的素数。我如何将这些素数的值存储在一个数组中并从该数组中打印出来？我尝试初始化 int[] n =1 但它根本不喜欢那样。谢谢你们！！！

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 + " ");
      }
    }
  }
}

采纳答案by Akira

Simply use an ArrayList to store all primes found.

只需使用 ArrayList 来存储找到的所有素数。

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 + " ");
        }
    }
}

回答by subash

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);

回答by Peter_James

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.

一个有效的素数查找器是“阿特金筛”，我将它存储在“欧拉计划”上的大多数问题中，而不是涉及素数。它可以在我的机器上计算多达 10 亿（不到一分钟）并打印出来。

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