I am printing out a list of prime numbers in a program and storing it an array. Then I want to get the the prime number on a particular index instead of the total list..
开发者_运维百科import java.util.*;
public class Gauss {
static int n;
static int[] array;
public static void Input() {
Scanner input = new Scanner(System.in);
System.out.println("Enter N: ");
n = input.nextInt();
}
public static boolean isPrime(int num) {
boolean prime = true;
int limit = (int) Math.sqrt(num);
for (int i = 2; i <= limit; i++) {
if (num % i == 0) {
prime = false;
break;
}
}
return prime;
}
public static void Calc() {
Input();
array = new int[1000];
for (int i = 2; i < array.length; i++) {
array[i] = i;
}
ArrayList<Integer> list = new ArrayList<Integer>(array.length);
for (int c : array) {
list.add(c);
}
list.remove(0);
list.remove(0);
Collections.sort(list);
for (int k : list) {
if (isPrime(k)) {
System.out.println(k);
}
}
}
public static void main(String[] args) {
Calc();
}
}
To get the nth prime just use array[n-1]
You might find this answer useful to a similar question.
And you can get the nth prime numbers with
List<Integer> primes = findPrimes(0, n);
System.out.println( primes.get(i) );
** EDIT **
Here is the integral test program that I came up (modified since the last posted answer above) with benchmark tests and all. I know there are faster implementations, and some optimizations can still be made, but here are some algorithms to generate prime numbers :
public class PrimeTests {
public static void main(String... args) {
AbstractPrimeGenerator[] generators = new AbstractPrimeGenerator[] {
new DefaultPrimeGenerator(),
new AtkinSievePrimeGenerator(),
new SundaramSievePrimeGenerator()
};
int[] primes;
int[] old_primes = null;
double[] testAvg = new double[generators.length];
long ts, te;
double time;
DecimalFormat df = new DecimalFormat("0.0######################");
int max = 10000000;
int testCountLoop = 10;
int it = 0, ti;
while (it++ < testCountLoop) {
ti = 0;
for (AbstractPrimeGenerator g : generators) {
ti++;
System.out.println(it + "." + ti + ". Calculating " + max
+ " primes numbers from " + g.getName() + "...");
ts = System.nanoTime();
primes = g.findPrimes(max);
te = System.nanoTime();
time = (te - ts) * Math.pow(10, -9) * 1000;
df.setRoundingMode(RoundingMode.HALF_UP);
testAvg[ti - 1] += time;
System.out.println("Found " + primes.length
+ " prime numbers (in " + time + " ms, "
+ df.format(time / primes.length) + " ms per prime)");
// for (int prime : primes) {
// System.out.print(prime + "... ");
// }
// System.out.println();
if (old_primes != null) {
System.out.print("Validating primes.... ");
if (primes.length == old_primes.length) {
for (int i = 0; i < primes.length; i++) {
if (primes[i] != old_primes[i]) {
System.out.println("Prime number does not match : " + primes[i] + " != " + old_primes[i] + " at index " + i);
System.exit(-1);
}
}
} else {
System.out.println("ERROR!! No match in prime results");
System.exit(-1);
}
System.out.println("Ok!");
}
old_primes = primes;
}
System.out.println("................");
}
System.out.println("Results:");
ti = 0;
for (AbstractPrimeGenerator g : generators) {
time = (testAvg[ti++] / testCountLoop);
System.out.println(ti + ". Average time finding " + max
+ " primes numbers from " + g.getName() + " = " + time
+ " ms or " + df.format(time / old_primes.length)
+ " ms per prime");
}
System.out.println("Done!");
}
/**
* Base class for a prime number generator
*/
static abstract public class AbstractPrimeGenerator {
/**
* The name of the generator
*
* @return String
*/
abstract public String getName();
/**
* Returns all the prime numbers where (2 <= p <= max)
*
* @param max
* int the maximum value to test for a prime
* @return int[] an array of prime numbers
*/
abstract public int[] findPrimes(int max);
}
/**
* Default naive prime number generator. Based on the assumption that any
* prime n is not divisible by any other prime m < n (or more precisely m <=
* sqrt(n))
*/
static public class DefaultPrimeGenerator extends AbstractPrimeGenerator {
@Override
public String getName() {
return "Default generator";
}
@Override
public int[] findPrimes(int max) {
int[] primes = new int[max];
int found = 0;
boolean isPrime;
// initial prime
if (max > 2) {
primes[found++] = 2;
for (int x = 3; x <= max; x += 2) {
isPrime = true; // prove it's not prime
for (int i = 0; i < found; i++) {
isPrime = x % primes[i] != 0; // x is not prime if it is
// divisible by p[i]
if (!isPrime || primes[i] * primes[i] > x) {
break;
}
}
if (isPrime) {
primes[found++] = x; // add x to our prime numbers
}
}
}
return Arrays.copyOf(primes, found);
}
}
/**
* Sieve of Atkin prime number generator Implementation following the Sieve
* of Atkin to generate prime numbers
*
* @see http://en.wikipedia.org/wiki/Sieve_of_Atkin
*/
static public class AtkinSievePrimeGenerator extends AbstractPrimeGenerator {
@Override
public String getName() {
return "Sieve of Atkin generator";
}
@Override
public int[] findPrimes(int max) {
boolean[] isPrime = new boolean[max + 1];
double sqrt = Math.sqrt(max);
for (int x = 1; x <= sqrt; x++) {
for (int y = 1; y <= sqrt; y++) {
int n = 4 * x * x + y * y;
if (n <= max && (n % 12 == 1 || n % 12 == 5)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x + y * y;
if (n <= max && (n % 12 == 7)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x - y * y;
if (x > y && (n <= max) && (n % 12 == 11)) {
isPrime[n] = !isPrime[n];
}
}
}
for (int n = 5; n <= sqrt; n++) {
if (isPrime[n]) {
int s = n * n;
for (int k = s; k <= max; k += s) {
isPrime[k] = false;
}
}
}
int[] primes = new int[max];
int found = 0;
if (max > 2) {
primes[found++] = 2;
}
if (max > 3) {
primes[found++] = 3;
}
for (int n = 5; n <= max; n += 2) {
if (isPrime[n]) {
primes[found++] = n;
}
}
return Arrays.copyOf(primes, found);
}
}
/**
* Sieve of Sundaram prime number generator Implementation following the
* Sieve of Sundaram to generate prime numbers
*
* @see http://en.wikipedia.org/wiki/Sieve_of_Sundaram
*/
static public class SundaramSievePrimeGenerator extends
AbstractPrimeGenerator {
@Override
public String getName() {
return "Sieve of Sundaram generator";
}
@Override
public int[] findPrimes(int max) {
int n = max / 2;
boolean[] isPrime = new boolean[max];
Arrays.fill(isPrime, true);
for (int i = 1; i < n; i++) {
for (int j = i; j <= (n - i) / (2 * i + 1); j++) {
isPrime[i + j + 2 * i * j] = false;
}
}
int[] primes = new int[max];
int found = 0;
if (max > 2) {
primes[found++] = 2;
}
for (int i = 1; i < n; i++) {
if (isPrime[i]) {
primes[found++] = i * 2 + 1;
}
}
return Arrays.copyOf(primes, found);
}
}
}
On my machine, the result gives :
Results:
1. Average time finding 10000000 primes numbers from Default generator = 1108.7848961000002 ms or 0.0016684019448402676 ms per prime
2. Average time finding 10000000 primes numbers from Sieve of Atkin generator = 199.8792727 ms or 0.0003007607413114167 ms per prime
3. Average time finding 10000000 primes numbers from Sieve of Sundaram generator = 132.6467922 ms or 0.00019959522073372766 ms per prime
Using one of the class's method above (you don't need the actual base class and all, only the actual method), you can do :
public class PrimeTest2 {
static public int[] findPrimes(int max) {
int[] primes = new int[max];
int found = 0;
boolean isPrime;
// initial prime
if (max > 2) {
primes[found++] = 2;
for (int x = 3; x <= max; x += 2) {
isPrime = true; // prove it's not prime
for (int i = 0; i < found; i++) {
isPrime = x % primes[i] != 0; // x is not prime if it is
// divisible by p[i]
if (!isPrime || primes[i] * primes[i] > x) {
break;
}
}
if (isPrime) {
primes[found++] = x; // add x to our prime numbers
}
}
}
return Arrays.copyOf(primes, found);
}
public static void main(String... args) {
Scanner input = new Scanner(System.in);
int MAX_N = Integer.MAX_VALUE / 100;
int n = 0;
while (n <= 0 || n >= MAX_N) {
System.out.print("Enter N: ");
n = input.nextInt();
if (n <= 0) {
System.out.println("n must be greater than 0");
}
if (n >= MAX_N) {
System.out.println("n must be smaller than " + MAX_N);
}
}
int max = n * 100; // just find enough prime numbers....
int[] primes = findPrimes(max);
System.out.println("Number of prime numbers found from " + 0 + " to "
+ max + " = " + primes.length);
System.out.println("The " + n
+ (n == 1 ? "st" : n == 2 ? "nd" : n == 3 ? "rd" : "th")
+ " prime number is : " + primes[n - 1]);
}
}
Which will output (for example) :
Enter N: 10000
Number of prime numbers found from 0 to 1000000 = 78498
The 10000th prime number is : 104729
With that in hand, you pretty have all that is to say about finding the nth prime number. For larger numbers (beyond int's), you'll have to modify the "default generator's" un-optimized method to accept long or use other methodologies (i.e. other language and/or libraries)
Cheers!
The code you have is pretty much the way to go, and Roflcopter's answer for picking the number is correct, but there is one optimization you could do that would significantly increase the performance. Instead of dividing by all numbers less than or equal to the square root, divide only by PRIMES less than or equal to the square root. Any number not divisible by any prime you've found so far is also not divisible by any combination of same, which is the definition of a nonprime number (having a prime factorization other than 1*N)
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论