Эратосфеновое сито без размножения, деления или петли "для" - PullRequest
Новая
       56

Эратосфеновое сито без размножения, деления или петли "для"

0 голосов
/ 21 апреля 2019

Мой друг и я работаем над домашним заданием в университете, чтобы сделать сито Эратосфена без всякого умножения, деления или петель for.Проблема в том, что я написал это до того, как наш профессор сказал нам не использовать эти вещи, и теперь я не знаю, что делать.Изменение циклов for на циклы while не представляет особой проблемы, но я понятия не имею, как избавиться от последнего умножения в конце кода.

Мой друг сделал некоторые изменения, которые я не понимаю (я прокомментирую изменения, которые он сделал), и я был бы очень благодарен, если бы кто-то мог объяснить, объясните мне их.В итоге:

  1. Нам нужно избавиться от for петель и заменить их на while петли

  2. Избавиться отумножение в конце кода, что является моей главной проблемой.

  3. Помогите понять изменения, отмеченные в комментариях.

Наш код: 

import java.util.Scanner;
public class primesieb {

    public static void main(String[] args) {
        //so we declare values and used the scanner to make an input.
        int input = 0;
        Scanner in = new Scanner(System.in);

        System.out.println("give an int bigger that 1:  ");
        input = in.nextInt();

        while (input <= 1)
        {
         //in case the number is smaller than 1.
                System.out.println("the Int must be bigger than 1!.");
                System.out.println("write an Int bigger than 1: ");
                input = in.nextInt(); 
        }
        in.close();
        //now first i wrote it without "+1" but my friend changed it to +1
           boolean[] x = new boolean[input + 1];
        //here I just wanted to add this to set that the position 0 in the string is not a prime number but after thinking I don't see its necessary

               x[0]=false;

        //he did write this commented for loop to assume that all of them are false but for me, it doesn't make sense, pls explain if it's necessary.
        //for (int i = 2; i < x.length; i++) {
          //  x[i] = false;}

        for (int i = 2; i < x.length; i++) {

            while (x[i]) 
            {
                i++;
            }
         // here how can we get rid of the multiplication.
        //the next for loop and if my friend did and a better explain would be nice helping me to represent my code better.
        for (int j = i; j*i < input; j++) 
            {
                x[i * j] = true;
            }
            if (! x[i] && i < input) 
            {
                System.out.println("the number" + i + "is prime. ");
            }
        }
    }       
}

Мы тестировали этот код на Eclipse, и он работал, но нам нужно избегать использования умножения.

1 Ответ

0 голосов
/ 21 апреля 2019

Во-первых, давайте упростим ввод вашего числа: 

    Scanner in = new Scanner(System.in);

    int input = 0;

    while (input <= 1) {
        System.out.println("Give an int bigger than 1: ");
        input = in.nextInt();

        if (input <= 1) {
            System.out.println("The int must be bigger than 1!.");
        }
    }

    in.close();

Минимизируя использование пробела, ваш друг не был прав насчет: 

//now first i wrote it without "+1" but my friend changed it to +1
boolean[] x = new boolean[input + 1];

x[0]=false;

Поскольку вы печатаете только простые числа меньшечем input (даже если input - простое число), и вы пропускаете 0 и 1, вы можете сделать x на три элемента короче: 

boolean x[] = new boolean[input - 2];  // all initialized to false

Любая петля for всегда можетразмотаться на цикл while: 

for (int i = 2; i < x.length; i++) {

Из трех элементов, разделенных точкой с запятой в настройке цикла for, первый идет перед циклом while, второй - while условие цикла, а третье - последний оператор в цикле while: 

int i = 2;

while (i < input) {  // 'input' instead of 'x.length' in our new design

    // (the rest of the code that follows below goes here)

    i++;
}

Это потенциальная проблема: 

while (x[i]) 
{
    i++;
}

Поскольку проверка границ на * 1028 не выполняется* до следующего x[i].Это работало для вас ранее из-за дополнительного неиспользуемого пространства, выделенного в x.Теперь нам нужно быть более точным: 

while (x[i - 2]) {
    if (++i >= input) {
        break outer;
    }
}

Мы используем i - 2, поскольку пропускаем пропущенные записи 0 и 1.Мы используем break outer; вместо просто break;, поскольку нам нужно выйти из цикла while, который включает этот цикл while.Итак, вернитесь и измените: 

while (i < input) {

выше вместо этого на: 

 outer: while (i < input) {

Преобразование этого цикла for несколько отличается из-за нежелательного умножения: 

for (int j = i; j*i < input; j++) {
    x[i * j] = true;
}

Мы собираемся многократно добавлять i вместо умножения на i.Это немного менее эффективно в начале, но в остальном хорошо: 

int j = i + i;

while (j < input) {
    x[j - 2] = true;
    j += i;
}

Этот тест не нужен: 

if (! x[i] && i < input)

Как мы уже знаем, x[i] - это false и i < inputиз нашей работы выше.Так что просто закончите с: 

System.out.println("The number " + i + " is prime.");

i++;  // we added this earlier to finish off our first 'for' to 'while' conversion

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

...