Java (Напишите программу, которая находила бы все простые числа в диапазоне от 2 до 100). Как эту жесть упростить?

Question

Java (Напишите программу, которая находила бы все простые числа в диапазоне от 2 до 100). Как эту жесть упростить?

Хаку Ученик (32), на голосовании 1 год назад

Я короче хотел с итерациями все дела, но потом понял что нет смысла дополнительно делить число на 4 и 8, если ты и так делишь его на 2
Нет смысла делить на 6 и 9, если ты делишь его на 3
Значит инкрементом не воспользоваться, просто прибавлять +2 тоже не вариант, потому что после 2 нужно делить на 3
Я хз как это делать, мой максимум это вот
Но там слишком много проверок

 class PrimeNumbers { 
    public static void main(String args[]) { 
        for (byte i = 2; i < 100; i++) { 
            if (((i > 0) && ((i % 2 != 0) && (i % 3 != 0) && (i % 5 != 0) && (i % 7 != 0))) ^ ((i == 2) || (i == 3) || (i == 5) || (i == 7))) { 
                System.out.println(i); 
            } 
        } 
    } 
}

Answer 1

Найти в инете алгоритм, реализация коего есть на всех языках на тысячах сайтов.
Во-первых, простые числа - ТОЛЬКО нечетные (кроме 2). Делить на 2 вообще нет смысла и проверять четные числа тоже. Скачите только по нечетным.
Остальные оптимизации нагуглите.

Answer 2

Sergey V. Voronin Искусственный Интеллект (292224) 1 год назад

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

ХакуУченик (32) 1 год назад

все работает
дак нужно сначала найти эти числа, а если нашел то и зачем массив
дак я и проверяю делимость на все числа, кроме 0, 1, 4, 6, 8, 9, потому что это бессмысленно

Sergey V. Voronin Искусственный Интеллект (292224) камшот, Не работает. Посмотрите список простых чисел, если не понимаете, где ошибка.

Sergey V. VoroninИскусственный Интеллект (292224) 1 год назад

...и кучи других простых чисел

Хаку Ученик (32) Sergey V. Voronin, "C:\Program Files\Java\jdk-20\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.4\lib\idea_rt.jar=56716:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.4\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath C:\Users\sasha\IdeaProjects\Test\out\production\Test PrimeNumbers 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Process finished with exit code 0

Answer 3

 class PrimeNumbers { 
    public static void main(String[] args) { 
        int n = 100; 
        boolean[] isPrime = new boolean[n + 1]; 
        for (int i = 2; i <= n; i++) { 
            isPrime[i] = true; 
        } 
        for (int i = 2; i * i <= n; i++) { 
            if (isPrime[i]) { 
                for (int j = i * i; j <= n; j += i) { 
                    isPrime[j] = false; 
                } 
            } 
        } 
        for (int i = 2; i <= n; i++) { 
            if (isPrime[i]) { 
                System.out.println(i); 
            } 
        } 
    } 
}

Этот алгоритм работает быстрее, чем ваш исходный код, и более эффективно находит все простые числа в заданном диапазоне.

Answer 4

Александр Искусственный Интеллект (301640) 1 год назад

рекурсия...

Answer 5

Самый быстрый алгоритм - это решето Эратосфена

 class PrimeNumbers {  
    public static void main(String args[]) {  
          
           int[] mas = new int[101]; 
		int len = mas.length; 
  
		for(int i = 2; i			for(int j = 2*i;j				if(mas[j]==0) { 
					mas[j] = 1; 
				} 
			} 
		} 
  
	for(int i = 2;i		if(mas[i]==0) { 
			System.out.println(i); 
		} 
	}
    }  
}

Понял фокус ?