Сито Java Eratostenes, печатающее только самое большое простое число с заданного потолка?

все! У меня есть java-приложение, которое показывает все простые числа от 2 до заданного числа (пользовательский ввод). Как я могу распечатать только последнее число, самое большое, которое я имею в виду, из заданного диапазона? Например: если пользовательский ввод равен 12, компилятор печатает только 11, а не 2,3,5,7,11. Вот код:

  package sieve_eratos;

   import java.util.Scanner;

   public class Sieve_Eratos {

public static void main(String[] args) {

    // get the ceiling on our prime numbers
    int N;
    Scanner sc = new Scanner(System.in);
    System.out.print("enter the prime number ceiling: ");
    N = sc.nextInt();
    sc.close();
    int k = 0;
    // init numbers array, where true denotes primality
    boolean[] isPrime = new boolean[N];
    // init possible primes
    isPrime[0] = false; // 1 is not prime
    for (int i = 1; i < N; i++) {
        isPrime[i] = true;
        k = k + 1;

    }


    // check every number >= 2 for primality
    for (int i = 2; i <= N; i++) {

        // i is prime if it hasn't been "crossed off" yet
        if (isPrime[i - 1]) {

            // print out the prime number
            System.out.println(i);



            // "cross off" all the subsequent multiples of i
            //for (int j = 2*i; j <= N; j += i) {
            for (int j = i * i; j <= N; j += i) { // more efficient
                isPrime[j - 1] = false;

            }

        }

    }
}
}

Я думал о создании еще одного целочисленного массива, а затем о вызове последнего элемента (который будет последним сохраненным числом), но я понятия не имею, как это сделать. Заранее спасибо!


java arrays loops sieve
person user2978170    schedule 11.11.2013    source источник
comment
Возможно, вы захотите использовать список вместо массива.   -  person Markus Koivisto    schedule 11.11.2013
comment
Почему бы не выполнить приведенную выше программу и после цикла for просто проверить свой массив в другом цикле for/while сзади наперед. Выведите число и остановитесь после первого найденного вами простого числа.   -  person Matthias    schedule 11.11.2013
comment
@MarkusKoivisto ключ к эффективности сита заключается в использовании массива, а не списка, чтобы иметь произвольный доступ. Подсчитывать и просто отмечать кратные, фактически не удаляя числа, чтобы сохранить возможность напрямую обращаться (и отмечать) к другим кратным.   -  person Will Ness    schedule 11.11.2013
comment
Да, в этом случае лучше просто сохранить индекс последнего найденного простого числа.   -  person Markus Koivisto    schedule 12.11.2013

Ответы (3)


arrow_upward
0
arrow_downward

Используйте NavigableSet.lower. Взгляните на следующий пример

Integer primeValues[]={2,3,5,7,11};//Here store all primes 
NavigableSet<Integer> primeCollec=new TreeSet<>();
primeCollec.addAll(Arrays.asList(primeValues));
                      //Add all range prime into NavigableSet

int input=12;// Get the user input here
int output=primeCollec.lower(input);// Here is the desired output based on input

System.out.println(output);
person Masudul    schedule 11.11.2013

arrow_upward
0
arrow_downward

Поскольку числа представляют собой последовательные числа (от 1 до N), мы можем проверить флаги простых чисел (в вашем коде это boolean[] isPrime) от самого большого индекса.

Если это правда, то сумма его индекса и 1 (индекс+1) будет искомым потолком простого числа.

Код выглядит следующим образом:

public static int populateCeilingPrime(boolean[] flags)
{
int len = flags.length;
for(int i= len -1;i>=0;i--)
{
    if(flags[i])
    {
        return i+1;
    }
}
return 0;
}

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

System.out.printf("The ceiling prime is %d ", populateCeilingPrime(isPrime));
person MouseLearnJava    schedule 11.11.2013

arrow_upward
0
arrow_downward

Вместо того, чтобы печатать простое число, вы можете проверить, больше ли число, которое вы хотите напечатать, чем какое-то более раннее число, которое вы хотели напечатать, а затем, если оно простое и больше, вы сохраните это простое число как самое большое на данный момент. Как только вы закончите процесс просеивания, этот сохраненный прайм должен быть тем, что вы хотите.

Вот так:

int maxPrime = 0;
for (int i = 2; i <= N; i++) {

    // i is prime if it hasn't been "crossed off" yet
    if (isPrime[i - 1]) {
        if(i > maxPrime) {
             maxPrime = i;
        }

        // "cross off" all the subsequent multiples of i
        //for (int j = 2*i; j <= N; j += i) {
        for (int j = i * i; j <= N; j += i) { // more efficient
            isPrime[j - 1] = false;

        }

    }

}
System.out.println(maxPrime);
person Jakob    schedule 11.11.2013
comment
это слишком много работы. почему бы не искать просеянный массив сверху, после того как он полностью просеян. Это шаг O(log N) вместо O(N/log N). - person Will Ness; 11.11.2013
comment
Я не понимаю, как много работы. Вместо того, чтобы выполнять еще один поиск, он будет иметь максимум, как только просеивание будет завершено. Но спорить не буду, я не анализировал свой подход с точки зрения сложности. - person Jakob; 12.11.2013
comment
вы выполняете операции O (N/log N) (обновляя переменную maxPrime для каждого найденного простого числа), чтобы сэкономить операции O (log N) (т.е. обратный отсчет от вершины массива до первой неотмеченной записи). с точки зрения сложности среднее расстояние между соседними простыми числами равно O(log N). - person Will Ness; 12.11.2013
comment
Не за что. :) Я должен был быть более ясным в своем первом комментарии. Это должно было быть почему бы не выполнить поиск в просеянном массиве сверху, после того, как он полностью просеян. Это O(log N) шагов вместо O(N/log N) шагов. - person Will Ness; 12.11.2013