Вычислить n-е простое число .. в Java? - PullRequest
Новая
       22

Вычислить n-е простое число .. в Java?

0 голосов
/ 12 января 2011

Я распечатываю список простых чисел в программе и сохраняю в нем массив. Затем я хочу получить простое число по определенному индексу вместо общего списка. 

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

Ответы [ 3 ]

4 голосов
/ 12 января 2011

Чтобы получить n-е простое число, просто используйте массив [n-1]

2 голосов
/ 12 января 2011

Вы можете найти этот ответ полезным для аналогичного вопроса.

И вы можете получить n-е простые числа с помощью 

List<Integer> primes = findPrimes(0, n);
System.out.println( primes.get(i) );

** РЕДАКТИРОВАТЬ **

Вот встроенная тестовая программа, которую я создал (модифицированная после последнего опубликованного ответа выше) с тестами производительности и всем остальным. Я знаю, что есть более быстрые реализации, и некоторые оптимизации все еще могут быть сделаны, но вот некоторые алгоритмы для генерации простых чисел: 

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

}

На моей машине результат дает: 

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

Используя один из методов класса выше (вам не нужен реальный базовый класс и все, только реальный метод), вы можете сделать: 

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

    }
}

Который будет выводить (например): 

Enter N: 10000
Number of prime numbers found from 0 to 1000000 = 78498
The 10000th prime number is : 104729

Имея это в виду, у вас есть все, что можно сказать о поиске n-го простого числа. Для больших чисел (кроме int) вам придется изменить неоптимизированный метод «генератора по умолчанию», чтобы он принимал long или использовать другие методологии (например, другой язык и / или библиотеки)

Ура!

0 голосов
/ 12 января 2011

Код, который у вас есть, в значительной степени подходит, и ответ Roflcopter на выбор числа правильный, но есть одна оптимизация, которую вы могли бы сделать, которая значительно повысила бы производительность.Вместо деления на все числа, меньшие или равные квадратному корню, делите только на ПРАЙМЫ, меньшие или равные квадратному корню.Любое число, не делимое ни на одно простое число, которое вы нашли до сих пор, также не делится на любую комбинацию из них, то есть определение не простого числа (с простой разложением, отличным от 1 * N)

...