Подтвердить что ты не робот

Вычисление и печать n-го простого числа

Я пытаюсь вычислить простые числа, которые я уже сделал. Но я хочу рассчитать и напечатать ТОЛЬКО n-е простое число (ввод пользователя), при вычислении остальных (они не будут напечатаны) будет напечатано только n-е простое число.

Вот что я написал до сих пор:

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number\n");
        System.out.printf("Please enter the nth prime number you want to find: ");
        n = input.nextInt();

        for(i = 2, x = 2; i <= n; i++) {
            for(x = 2; x < i; x++) {
                if(i % x == 0) {
                    break;
                }
            }
            if(x == i) {
                System.out.printf("\n%d is prime", x);
            }
        }
    }
}

Это программа, которую я написал для вычисления простых чисел от 1 до n. Тем не менее, я хочу, чтобы он печатал только n-мерное число,

То, что я думал делать, - это делать какой-то счетчик int и ++, каждый раз, когда он находит штрих, а когда count == n, то он печатает это число, но я не могу понять как приземлиться.

4b9b3361

Ответ 1

Для вычисления n-го числа я знаю два основных варианта.

Простой способ

То есть, чтобы подсчитать все простые числа, начиная с 2, когда вы их найдете, пока не достигнете нужного n th.

Это можно сделать с разными уровнями сложности и эффективности, и есть два концептуально разных способа сделать это. Первый -

Проверка правильности всех чисел в последовательности

Это будет выполняться с помощью функции драйвера, например

public static int nthPrime(int n) {
    int candidate, count;
    for(candidate = 2, count = 0; count < n; ++candidate) {
        if (isPrime(candidate)) {
            ++count;
        }
    }
    // The candidate has been incremented once after the count reached n
    return candidate-1;
}

и интересной частью, определяющей эффективность, является функция isPrime.

Очевидный способ проверки правильности, учитывая определение штриха как числа больше единицы, которое делится только на 1 и само по себе, что мы узнали в школе¹,

Пробное деление

Прямой перевод определения в код

private static boolean isPrime(int n) {
    for(int i = 2; i < n; ++i) {
        if (n % i == 0) {
            // We are naive, but not stupid, if
            // the number has a divisor other
            // than 1 or itself, we return immediately.
            return false;
        }
    }
    return true;
}

но, как вы скоро обнаружите, если попробуете, его простота сопровождается медлительностью. С этим испытанием primality вы можете найти 1000 th prime, 7919, за несколько миллисекунд (около 20 на моем компьютере), но нахождение 10000 th prime, 104729, занимает секунды (~ 2,4 с), 100000 th prime, 1299709, несколько минут (около 5), миллионное премьер, 15485863, заняло бы около восьми с половиной часов, десятимиллионное премьер, 179424673, недели и т.д. Сложность выполнения хуже, чем квадратичная - Θ (n² * log n).

Итак, мы хотели бы немного ускорить тестирование приматов. Шаг, который принимает много людей, - это осознание того, что делитель n (кроме самого n) может быть не более n/2. Если мы используем этот факт и пусть цикл пробного деления будет выполняться только до n/2 вместо n-1, как изменяется время работы алгоритма? Для составных чисел предел нижнего цикла ничего не меняет. Для простых чисел количество пробных подразделений сокращается вдвое, поэтому в целом время работы должно быть уменьшено в несколько раз меньшем, чем 2. Если вы попробуете это, вы обнаружите, что время работы почти в два раза меньше, поэтому почти все время тратится на проверку примитивности простых чисел, несмотря на то, что имеется гораздо больше композитов, чем простых.

Теперь это не помогло, если мы хотим найти стомиллионный премьер, поэтому нам нужно сделать лучше. Пытаясь еще больше сократить предел цикла, давайте посмотрим, для каких чисел необходима верхняя граница n/2. Если n/2 является делителем n, то n/2 является целым числом, другими словами, n делится на 2. Но тогда цикл не проходит мимо 2, поэтому он никогда (кроме n = 4) достигает n/2. Весело хорошо, так что следующий наибольший возможный делитель n? Почему, n/3, конечно. Но n/3 может быть только делителем n, если он является целым числом, другими словами, если n делится на 3. Тогда цикл будет выходить с 3 (или раньше, в 2) и никогда не достигнет n/3 (кроме n = 9). Следующий наибольший возможный делитель...

Подождите минуту! Имеем 2 <-> n/2 и 3 <-> n/3. Делители n попадают в пары.

Если мы рассмотрим пару (d, n/d) соответствующих делителей n, либо d = n/d, т.е. d = √n, либо один из них, скажем, d, меньше другого. Но тогда d*d < d*(n/d) = n и d < √n. Каждая пара соответствующих делителей n содержит (по крайней мере) ту, которая не превосходит √n.

Если n является составным, его наименьший нетривиальный делитель не превышает √n.

Таким образом, мы можем уменьшить предел цикла до √n, что уменьшает сложность выполнения алгоритма во время выполнения. Теперь он должен быть Θ (n 1,5 * √ (log n)), но эмпирически он, похоже, немного улучшится, однако недостаточно данных, чтобы сделать надежные выводы из эмпирических результатов.

Это находит миллионный премьер за примерно 16 секунд, десятимиллионный за девять минут, и он найдет сто миллионный за четыре с половиной часа. Это все еще медленно, но далеко от десяти лет или около того это займет наивное пробное разделение.

Так как существуют квадраты простых чисел и произведений двух близких чисел, например 323 = 17 * 19, мы не можем уменьшить предел для цикла пробного деления ниже √n. Поэтому, находясь с пробным делением, мы должны искать другие способы улучшения алгоритма.

Можно легко заметить, что нет простого числа, отличного от 2, поэтому нам нужно только проверять нечетные числа после того, как мы позаботились о 2. Это не имеет большого значения, хотя, поскольку четные числа являются самый дешевый, чтобы найти композитный материал, и большая часть времени все еще проводится, проверяя приматов простых чисел. Однако, если мы посмотрим на четные числа в качестве кандидатов-делителей, мы увидим, что если n делится на четное число, n сам должен быть четным, поэтому (кроме 2) он будет признан составным до деления на любое четное число больше 2. Таким образом, все деления на четные числа больше 2, которые встречаются в алгоритме, должны обязательно оставить ненулевой остаток. Таким образом, мы можем опустить эти деления и проверить делимость только на 2 и нечетные числа от 3 до √n. Это половина (не совсем точно) количества делений, необходимых для определения числа как простого или составного и, следовательно, времени выполнения. Это хорошее начало, но можем ли мы сделать лучше?

Другое большое семейство чисел - это кратность 3. Каждое третье деление, которое мы выполняем, кратно 3, но если n делится на один из них, он также делится на 3 и, следовательно, не делит на 9, 15, 21,..., которые мы выполняем в нашем алгоритме, всегда оставят остаток от 0. Итак, как мы можем пропустить эти подразделения? Ну, числа, не делящиеся ни на 2, ни на 3, точно являются числами формы 6*k ± 1. Начиная с 5 (поскольку нас интересуют только цифры, превышающие 1), это 5, 7, 11, 13, 17, 19,..., шаг от одного до следующего чередует между 2 и 4, что достаточно легко, поэтому мы можем использовать

private static boolean isPrime(int n) {
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int step = 4, m = (int)Math.sqrt(n) + 1;
    for(int i = 5; i < m; step = 6-step, i += step) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

Это дает нам еще одно ускорение в размере (почти) 1,5, поэтому нам понадобится около полутора часов до ста миллионного простого.

Если мы продолжим этот маршрут, следующим шагом будет устранение кратных 5. Числа, совпадающие с 2, 3 и 5, являются числами формы

30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29

поэтому нам нужно будет делить на восемь из каждых тридцати чисел (плюс три наименьших простых числа). Шаги от одного к следующему, начиная с 7, проходят через 4, 2, 4, 2, 4, 6, 2, 6. Это все еще достаточно просто для реализации и дает другое ускорение в 1,25 раза (минус бит для более сложный код). Идем дальше, кратные 7 будут устранены, оставив 48 из каждых 210 чисел, чтобы разделить их, затем 11 (480/2310), 13 (5760/30030) и так далее. Каждый штрих p, у которого кратные удалены, дает ускорение (почти) p/(p-1), поэтому возврат уменьшается, а стоимость (сложность кода, пространство для таблицы поиска шагов) увеличивается с каждым простым числом.

В общем, можно было бы прекратить скоро, после устранения кратных, возможно, шести или семи простых чисел (или даже меньше). Здесь, однако, мы можем проследить до конца, когда кратные всех простых чисел были устранены, и только простые числа оставлены в качестве кандидатов-делителей. Поскольку мы находим все простые числа в порядке, каждое число найдено до того, как оно понадобится в качестве кандидата-делителя и затем может быть сохранено для будущего использования. Это уменьшает алгоритмическую сложность - если я не просчитался - O (n 1,5/√ (log n)). За счет использования пространства для хранения простых чисел.

С пробным делением, это так же хорошо, как и получается, вам нужно попытаться разделить все простые числа на √n или первое деление n, чтобы определить примитивность n. Это находит стомиллионное премьеру через полчаса.

Итак, как насчет

Быстрые тесты прочности

У простых чисел есть другие теоретико-числовые свойства, чем отсутствие нетривиальных делителей, которые, как правило, не имеют составных чисел. Такие свойства, если они быстро проверяются, могут стать основой вероятностных или детерминированных тестов примитивности. Архетипическое такое свойство связано с именем Пьера де Ферма, который в начале 17 века th обнаружил, что

Если p является простым, то p является дивизором (a p -a) для всех a.

Это - Ферма, так называемая "небольшая теорема", - в эквивалентной формулировке

Пусть p - простое и a не делимое на p. Тогда p делит a p-1 - 1.

основу большинства широко распространенных быстрых тестов прочности (например, Миллер-Рабин), а также варианты или аналоги, которые появляются еще более (например, Lucas-Selfridge).

Итак, если мы хотим знать, является ли не слишком маленькое нечетное число n простым (четные и малые числа эффективно обрабатываются пробным делением), мы можем выбрать любое число a ( > 1), которое не является кратное n, например, 2, и проверьте, делит ли n на n-1 - 1. Так как a n-1 становится огромным, это больше эффективно выполняется путем проверки того, a^(n-1) ≡ 1 (mod n), т.е. модулярным возведением в степень. Если эта конгруэнтность не выполняется, мы знаем, что n является составной. Однако, если оно выполнено, мы не можем заключить, что n является простым, например 2^340 ≡ 1 (mod 341), но 341 = 11 * 31 является составным. Композитные числа n такие, что a^(n-1) ≡ 1 (mod n) называются псевдомарами Ферма для базы a.

Но такие случаи встречаются редко. Учитывая любое основание a > 1, хотя в базе a существует бесконечное число псевдопространств Ферма, они намного реже реальных простых чисел. Например, существует только 78 псевдопространств Fermat 2-го оснований и 76 псевдо-премьеров Fermat 76 ниже 100000, но 9592 простых. Поэтому, если выбрать произвольный нечетный n > 1 и произвольную базу a > 1 и находит a^(n-1) ≡ 1 (mod n), есть хорошая вероятность, что n на самом деле просто.

Однако мы находимся в несколько иной ситуации, нам дают n и можем выбрать только a. Итак, для нечетного композитного n, для которого a, 1 < a < n-1 может a^(n-1) ≡ 1 (mod n) удержать? К сожалению, есть составные числа - числа Кармайкл - такие, что сравнение выполняется для каждого a взаимно простого к n. Это означает, что для того, чтобы идентифицировать число Кармайчеля как составное с тестом Ферма, мы должны выбрать базу, которая кратно одному из n простых делителей - их может не быть много.

Но мы можем усилить тест Fermat, чтобы композиты были более надежно обнаружены. Если p - нечетное простое число, напишите p-1 = 2*m. Тогда, если 0 < a < p,

a^(p-1) - 1 = (a^m + 1) * (a^m - 1)

и p делит ровно один из двух факторов (два фактора различаются на 2, поэтому их наибольший общий делитель равен 1 или 2). Если m четное, мы можем разделить a^m - 1 таким же образом. Продолжая, если p-1 = 2^s * k с k нечетным, напишите

a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)

то p делит ровно один из факторов. Это приводит к сильному тесту Ферма,

Пусть n > 2 - нечетное число. Напишите n-1 = 2^s * k с k нечетным. Для любого a с 1 < a < n-1, если

  • a^k ≡ 1 (mod n) или
  • a^((2^j)*k) ≡ -1 (mod n) для любого j с 0 <= j < s

то n является сильным (Ферма) вероятным простым для базы a. Сложное сильное основание a (Ферма) вероятное простое называется сильным (Ферматом) псевдопереводом для базы a. Сильные псевдопермы Ферма даже реже, чем обычные псевдомары Ферма, ниже 1000000, есть 78498 простых чисел, 245 базисных 2 Fermat псевдопроизмов и только 46 базовых псевдомоментов Fermat. Что еще более важно, для любого нечетного композита n существует не более (n-9)/4 базиса 1 < a < n-1, для которых n является сильным псевдоприемом Ферма.

Итак, если n является нечетным композитом, вероятность того, что n проходит k сильные тесты Ферма со случайно выбранными основами между 1 и n-1 (эксклюзивные оценки), меньше 1/4^k.

Сильный тест Fermat принимает шаги O (log n), каждый шаг включает в себя одно или два умножения чисел с O (log n) битами, поэтому сложность O ((log n) ^ 3) с наивным умножением [для огромный n, более сложные алгоритмы умножения могут оказаться полезными].

Тест Миллера-Рабина - это сильное испытание Fermat с k-кратным временем со случайно выбранными основами. Это вероятностный тест, но при достаточно малых границах известны короткие комбинации оснований, которые дают детерминированный результат.

Сильные тесты Fermat являются частью детерминированного теста APRCL.

Целесообразно предшествовать таким испытаниям пробным делением на первые несколько небольших простых чисел, поскольку деления сравнительно дешевы и что сорняки большинства композитов.

Для задачи нахождения n th prime, в диапазоне, где можно проверить все числа для примитивности, существуют известные комбинации оснований, которые делают множественный сильный тест Ферма правильным, поэтому что даст более быстрый алгоритм O (n * (log n) 4).

Для n < 2^32 основания 2, 7 и 61 достаточны для проверки первобытности. Используя это, стомиллионное простое обнаружено примерно через шесть минут.

Устранение композитов с помощью простых делителей, Сито Эратосфена

Вместо того, чтобы исследовать числа в последовательности и проверять, является ли каждое из простых с нуля, можно также рассмотреть весь набор соответствующих чисел как одну часть и исключить кратные заданного простого за один раз. Это известно как Сито Эратосфена:

Чтобы найти простые числа, не превышающие n

  • составить список всех чисел от 2 до n
  • для каждого k от 2 до n: если k еще не перечеркнуто, оно простое; сбрасывать все кратные k как композиты

Простые числа - это номера в списке, которые не пересекаются.

Этот алгоритм принципиально отличается от пробного деления, хотя оба непосредственно используют делимость характеристик простых чисел, в отличие от теста Ферма и аналогичных тестов, которые используют другие свойства простых чисел.

В пробном делении каждое число n сопряжено со всеми простыми числами, не превышающими меньшее из √n и наименьшим простым делителем n. Так как большинство композитов имеют очень малый простой делитель, то в среднем обнаружение композитов здесь дешево. Но тестовые простые числа стоят дорого, так как существует относительно много простых значений ниже √n. Несмотря на то, что существует много композитов, чем простых, стоимость тестирования простых чисел настолько высока, что полностью доминирует в общем времени работы и делает пробное деление относительно медленным алгоритмом. Пробное деление для всех чисел меньше n принимает шаги O (N 1,5/(log N) ²).

В сите каждый составной n сопряжен со всеми его простыми делителями, но только с ними. Таким образом, простые числа - это дешевые цифры, их только когда-то смотрят, а композиты стоят дороже, их много раз сбрасывают. Можно было бы подумать, что, поскольку сито содержит гораздо больше "дорогих" чисел, чем "дешевые", в целом это был бы плохой алгоритм. Однако составное число не имеет много различных простых делителей - число различных простых делителей в n ограничено log n, но обычно оно намного меньше, среднее числа различных простых делителей чисел <= n log log n - поэтому даже "дорогие" числа в сите в среднем не более (или чуть больше) дороже, чем "дешевые" номера для пробного деления.

Просеивание до n, для каждого простого p есть Θ(N/p) кратность для скрещивания, поэтому общее число переходов составляет Θ(∑ (N/p)) = Θ(N * log (log N)). Это дает более быстрые алгоритмы для поиска простых чисел до n, чем пробное деление или последовательное тестирование с более быстрыми критериями прочности.

Однако в сите есть недостаток, он использует память O(N). (Но с сегментированным ситом, которое может быть уменьшено до O(√N) без увеличения временной сложности.)

Для нахождения n th prime вместо простых чисел до n существует также проблема, о которой заранее не известно, как далеко должно пройти сито.

Последнее можно решить, используя теорему о простом числе. PNT говорит

π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1),

где π(x) - число простых чисел, не превышающих x (здесь и ниже, log должен быть естественным логарифмом, для алгоритмических сложностей не важно, какая база выбрана для логарифмов). Из этого следует, что p(n) ~ n*log n, где p(n) - это n th prime, и для p(n) имеются хорошие верхние оценки для p(n), в частности

n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.

Таким образом, можно использовать это как предел просеивания, он далеко не превышает цель.

Требование пространства O(N) можно преодолеть, используя сегментированное сито. Затем можно записать простые числа ниже √n для O(√N / log N) потребления памяти и использовать сегменты увеличивающейся длины (O (√N), когда сито близко к N).

Есть несколько простых улучшений в алгоритме, как указано выше:

  • начните сбрасывать кратность p только при , а не в 2*p
  • устранить четные числа из сита
  • устранить кратные дальнейшие мелкие простые числа из сита

Ни один из них не уменьшает алгоритмическую сложность, но все они уменьшают постоянные факторы на значительную величину (как и при пробном делении, исключение кратных p дает меньшее ускорение для более крупного p, одновременно увеличивая сложность кода чем для меньшего p).

Использование первых двух улучшений дает

// Entry k in the array represents the number 2*k+3, so we have to do
// a bit of arithmetic to get the indices right.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    int limit, root, count = 1;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit) + 1;
    limit = (limit-1)/2;
    root = root/2 - 1;
    boolean[] sieve = new boolean[limit];
    for(int i = 0; i < root; ++i) {
        if (!sieve[i]) {
            ++count;
            for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) {
                sieve[j] = true;
            }
        }
    }
    int p;
    for(p = root; count < n; ++p) {
        if (!sieve[p]) {
            ++count;
        }
    }
    return 2*p+1;
}

который находит стомиллионный премьер, 2038074743, примерно через 18 секунд. Это время может быть уменьшено примерно до 15 секунд (здесь YMMV), сохраняя флаги упакованными, по одному биту на флаг, а не как boolean s, так как сокращение использования памяти дает лучшую локальность кэша.

Упаковка флагов, исключая также кратные 3 и используя бит-twiddling для более быстрого счета,

// Count number of set bits in an int
public static int popCount(int n) {
    n -= (n >>> 1) & 0x55555555;
    n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
    n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
    return (n * 0x01010101) >> 24;
}

// Speed up counting by counting the primes per
// array slot and not individually. This yields
// another factor of about 1.24 or so.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    if (n == 3) return 5;
    int limit, root, count = 2;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit);
    switch(limit%6) {
        case 0:
            limit = 2*(limit/6) - 1;
            break;
        case 5:
            limit = 2*(limit/6) + 1;
            break;
        default:
            limit = 2*(limit/6);
    }
    switch(root%6) {
        case 0:
            root = 2*(root/6) - 1;
            break;
        case 5:
            root = 2*(root/6) + 1;
            break;
        default:
            root = 2*(root/6);
    }
    int dim = (limit+31) >> 5;
    int[] sieve = new int[dim];
    for(int i = 0; i < root; ++i) {
        if ((sieve[i >> 5] & (1 << (i&31))) == 0) {
            int start, s1, s2;
            if ((i & 1) == 1) {
                start = i*(3*i+8)+4;
                s1 = 4*i+5;
                s2 = 2*i+3;
            } else {
                start = i*(3*i+10)+7;
                s1 = 2*i+3;
                s2 = 4*i+7;
            }
            for(int j = start; j < limit; j += s2) {
                sieve[j >> 5] |= 1 << (j&31);
                j += s1;
                if (j >= limit) break;
                sieve[j >> 5] |= 1 << (j&31);
            }
        }
    }
    int i;
    for(i = 0; count < n; ++i) {
        count += popCount(~sieve[i]);
    }
    --i;
    int mask = ~sieve[i];
    int p;
    for(p = 31; count >= n; --p) {
        count -= (mask >> p) & 1;
    }
    return 3*(p+(i<<5))+7+(p&1);
}

находит стомиллионное простое около 9 секунд, что не является невыносимо длинным.

Существуют другие типы первичных сит, представляющих особый интерес - сито Аткина, которое использует тот факт, что некоторые классы сопоставлений (рациональных) простых чисел являются композитами в кольце алгебраических целых чисел некоторых квадратичных расширений ℚ. Здесь нет места для расширения математической теории, достаточно сказать, что сито Аткина имеет более низкую алгоритмическую сложность, чем сито Эратосфена, и, следовательно, предпочтительнее для больших пределов (для небольших пределов не слишком оптимизированное сито Аткина имеет более высокий накладные расходы и, следовательно, могут быть медленнее, чем сравнимое оптимизированное сито Eratoshenes). DJ Bernstein primegen библиотека (написанная на C) хорошо оптимизирована для чисел ниже 2 32 и находит сто- миллионное простое (здесь) примерно через 1,1 секунды.

Быстрый способ

Если мы хотим найти только n th prime, нет никакого внутреннего значения для нахождения всех меньших простых чисел. Если мы сможем пропустить большинство из них, мы сможем сэкономить много времени и работать. Учитывая хорошее приближение a(n) к n th prime p(n), если мы имеем быстрый способ вычисления числа простых чисел π(a(n)), не превышающих a(n), тогда мы можем просеять небольшой диапазон выше или ниже a(n), чтобы идентифицировать несколько отсутствующих или избыточных простых чисел между a(n) и p(n).

Мы видели легко вычисленное довольно хорошее приближение к p(n) выше, мы могли бы взять

a(n) = n*(log n + log (log n))

например.

Хорошим методом вычисления π(x) является метод здесь, если кто-то хочет поиграть с ними.


¹ Помимо замечаний для чрезмерно заинтересованных душ: определение простых чисел, используемых в современной математике, различно, применимо в гораздо более общих ситуациях. Если мы адаптируем определение школы к отрицательным числам - поэтому число является простым, если оно не равно 1 или -1 и не делится только на 1, -1, само и его отрицательное - которое определяет (для целых) то, что в настоящее время называется неприводимым элементом из ℤ, однако, для целых чисел определения простых и неприводимых элементов совпадают.

Ответ 2

int counter = 0;

for(int i = 1; ; i++) {
    if(isPrime(i)
        counter++;

    if(counter == userInput) {
        print(i);
        break;
    }
}

Изменить: ваша основная функция может использовать немного работы. Вот тот, который я написал:

private static boolean isPrime(long n) {
    if(n < 2)
        return false;

    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Примечание. При просмотре факторов вам нужно только перейти к sqrt (n), следовательно i * i <= n

Ответ 3

Вы пытаетесь сделать слишком много в основном методе. Вам нужно разбить это на более управляемые части. Напишите метод boolean isPrime(int n), который возвращает true, если число является простым, а false в противном случае. Затем измените основной метод использования isPrime.

Ответ 4

java.math.BigInteger имеет следующий методProbablePrime(). Хотя я предполагаю, что это предназначено для криптографии, вы можете использовать его для работы.

BigInteger prime = BigInteger.valueOf(0);
for (int i = 0; i < n; i++) {
    prime = prime.nextProbablePrime();
}
System.out.println(prime.intValue());

Ответ 5

Я просто добавил недостающие строки в свой собственный процесс мышления.

static int nthPrimeFinder (int n) {

    int counter = 1; // For 1 and 2. assuming n is not 1 or 2.
    int i = 2;
    int x = 2;
    int tempLength = n;

    while (counter <= n) {
        for (; i <= tempLength; i++) {
            for (x = 2; x < i; x++) {
                if (i % x == 0) {
                    break;
                }
            }
            if (x == i && counter < n) {
                //System.out.printf("\n%d is prime", x);
                counter++;
                if (counter == n) {
                    System.out.printf("\n%d is prime", x);
                    return counter;
                }
            }
        }
        tempLength = tempLength+n;
    }
    return 0;
}

Ответ 6

public class prime{
    public static void main(String ar[])
    {
      int count;
      int no=0;
      for(int i=0;i<1000;i++){
        count=0;
        for(int j=1;j<=i;j++){

        if(i%j==0){
          count++;
         }
        }
        if(count==2){
          no++;
          if(no==Integer.parseInt(ar[0])){
            System.out.println(no+"\t"+i+"\t") ;
          }
        }
      }
    }
}

Ответ 7

Я вижу, что вы получили много правильных ответов и очень подробный. Я считаю, что вы не проверяете его на очень большие простые числа. И ваша единственная проблема заключается в том, чтобы избежать печати промежуточного простого числа вашей программой.

Небольшое изменение вашей программы сделает трюк.

Сохраняйте свою логику таким же образом и просто вытащите инструкцию печати вне цикла. Разрыв внешней петли после n простых чисел.

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number\n");
        System.out.printf("Please enter the nth prime number you want to find:");
        n = input.nextInt();

        for(i = 2, x = 2; n > 0; i++) {
            for(x = 2; x < i; x++) {
                if(i % x == 0) {
                    break;
                }
            }
            if(x == i) {
                n--;
            }
        }
        System.out.printf("\n%d is prime", x);

    }
}

Ответ 8

Использование Java 8 parallelStream будет быстрее. Ниже приведен мой код для поиска N-го простого числа

public static Integer findNthPrimeNumber(Integer nthNumber) {
    List<Integer> primeList = new ArrayList<>();
    primeList.addAll(Arrays.asList(2, 3));
    Integer initializer = 4;
    while (primeList.size() < nthNumber) {
        if (isPrime(initializer, primeList)) {
            primeList.add(initializer);
        }
        initializer++;
    }
    return primeList.get(primeList.size() - 1);
}

public static Boolean isPrime(Integer input, List<Integer> primeList) {
    return !(primeList.parallelStream().anyMatch(i -> input % i == 0));
}

@Test
public void findNthPrimeTest() {
    Problem7 inputObj = new Problem7();
    Integer methodOutput = inputObj.findNthPrimeNumber(100);
    Assert.assertEquals((Integer) 541, methodOutput);
    Assert.assertEquals((Integer) 104743, inputObj.findNthPrimeNumber(10001));
}

Ответ 9

Хотя имеется много правильных и подробных объяснений. но вот мой C:

#include<stdio.h>
#include<conio.h> 

main()
{
int pk,qd,am,no,c=0;
printf("\n Enter the Number U want to Find");
scanf("%d",&no);
for(pk=2;pk<=1000;pk++)
{
am=0;
for(qd=2;qd<=pk/2;qd++)
{
if(pk%qd==0)
{
am=1;
break;
}}
if(am==0)
c++;
if(c==no)
{
printf("%d",pk);
break;
}}
getch();
return 0;
}