Как вспомнить функцию, Решето Эратосфена

Я пытаюсь написать код, который будет вычислять простые числа с помощью решета Эратосфена. Я должен включить функцию, которая будет принимать число и пересекать все числа, кратные этому числу. Для тестирования я установил первое число равным 2, а второе - 3. Это работает для первого числа, но никогда для второго (независимо от порядка чисел, т.е. если я сначала введу 3 в функцию). Я знаю, что есть и другие завершенные сита Эратосфена, но я хотел попробовать сделать это так, как я придумал в первую очередь.

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner input = new Scanner(System.in);
    System.out.println("Which number would you like to calculate up to?");
    int n = input.nextInt();
    input.close();

    int x = 0;
    int newNumber = 2;
    int numbers[] = new int[n];
    while(newNumber <= n){
        numbers[x] = newNumber;
        x++;
        newNumber++;
    }

    int currentNumber = 2; 
    int finalNumber[] = markOfMultiples(n, numbers, currentNumber);
    for(int y = 0;y < n-1;y++){
        System.out.print(finalNumber[y] + ", ");
    }

    currentNumber = 3; 
    int secondNumber[] = markOfMultiples(n, numbers, currentNumber);
    for(int y = 0;y < n-1;y++){
        System.out.println(secondNumber[y]);
    }

}

public static int[] markOfMultiples(int n, int numbers[], int currentNumber){

    int originalNumber = currentNumber;
    while(currentNumber<n){
        currentNumber = currentNumber + originalNumber;
        int count2 = 0;
        while(currentNumber != numbers[count2] && currentNumber<=n && count2<n){            
            count2++;
        }
        numbers[count2] = 0;
    }
    return numbers;
}

Я получаю сообщение об ошибке: Исключение в потоке "main" java.lang.ArrayIndexOutOfBoundsException: 20

в ситеЭратосфена.ситоЭратосфена.маркамножеств(ситоЭратосфена.java:46)

на ситеЭратосфена.ситоЭратосфена.main(ситоЭратосфена.java:28)

Строка 28, когда я вспоминаю функцию: int secondNumber[] = markOfMultiples(n, numbers, currentNumber);

И строка 46 while(currentNumber != numbers[count2] && currentNumber<=n && count2<20){

Любая помощь приветствуется. Как мне продолжать вызывать функцию?

p.s. Пожалуйста, извините за имена переменных, так как я изменю их, когда программа заработает.


java sieve-of-eratosthenes
person hughdini    schedule 19.01.2015    source источник
comment
Это школьное задание? Мы делаем это в моей школе.   -  person Malik Brahimi    schedule 19.01.2015
comment
Да, это школьное задание   -  person hughdini    schedule 19.01.2015
comment
в Java вы можете получить длину массива, например. числа.длина; нет необходимости передавать отдельный параметр длины массива.   -  person Sbodd    schedule 20.01.2015

Ответы (2)


arrow_upward
3
arrow_downward

Если вы хотите, чтобы этот подход работал, вы можете сделать исправление, рекомендованное @Thierry, чтобы сначала проверить count2 < n в цикле while, а затем также окружить строку

numbers[count2] = 0

с предложением if для проверки count2 не выходит за пределы индекса. например

if (count2 < n) {
    numbers[count2] = 0;
}

Ваша последняя задача — как вызвать функцию markOfMultiples() достаточное количество раз, когда n становится немного больше. Это не проблема с вашим фундаментальным подходом - вы определенно можете это сделать, и ваш подход будет работать хорошо и иметь приемлемую производительность для небольших чисел (скажем, до 10000).

Однако

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

  1. Читабельность — будет ли легко тому, кто просматривает (маркирует) ваш код, чтобы понять, что он делает, и убедиться, что он будет работать правильно для всех значений n?

  2. Старайтесь не повторяться - например, подумайте, где вы заполняете свой массив numbers:

    while(newNumber <= n){
   numbers[x] = newNumber;
   x++;
   newNumber++;
}

    Будет ли когда-нибудь x отличаться от newNumber? Вам нужны обе переменные? Такая сортировка или повторение происходит где-то в вашем коде — принцип, которого следует придерживаться, известен как СУХОЙ Повторяйте сами)

  3. Есть ли более простой способ переместить индекс на originalNumber позиций в вашем markOfMultiples() методе? (ПОДСКАЗКА: да, есть)

  4. Вам действительно нужны фактические числа в массиве numbers[]? Вы получите много нулей и простых чисел, оставленных как целые значения, если вы решите, как многократно вызывать ваш markOfMultiples для высоких значений n. Будет ли массив из 1 и 0 (или true и false) достаточным, если вы использовали индекс массива, чтобы получить простое число?

person J Richard Snape    schedule 19.01.2015

arrow_upward
1
arrow_downward

Вам нужно проверить, если count2 ‹ n ПЕРЕД доступом к числам [count2]:

while(count2 < n && currentNumber != numbers[count2] && currentNumber<= n){            
    count2++;
}
person Thierry    schedule 19.01.2015
comment
@bike3 с таким же исключением? - person Thierry; 19.01.2015
comment
извините, я забыл упомянуть, теперь он говорит, что есть проблема со строкой 50 numbers[count2] = 0; - person hughdini; 19.01.2015