Java (Напишите программу, которая находила бы все простые числа в диапазоне от 2 до 100). Как эту жесть упростить?
Я короче хотел с итерациями все дела, но потом понял что нет смысла дополнительно делить число на 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);
}
}
}
} Найти в инете алгоритм, реализация коего есть на всех языках на тысячах сайтов.
Во-первых, простые числа - ТОЛЬКО нечетные (кроме 2). Делить на 2 вообще нет смысла и проверять четные числа тоже. Скачите только по нечетным.
Остальные оптимизации нагуглите.
Самый быстрый алгоритм - это решето Эратосфена
class PrimeNumbers {
public static void main(String args[]) {
int[] mas = new int[101];
int len = mas.length;
for(int i = 2; i<len; ++i) {
for(int j = 2*i;j<len;j+=i) {
if(mas[j]==0) {
mas[j] = 1;
}
}
}
for(int i = 2;i<len;++i) {
if(mas[i]==0) {
System.out.println(i);
}
}
}
} Понял фокус ?
рекурсия...
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);
}
}
}
}
Этот алгоритм работает быстрее, чем ваш исходный код, и более эффективно находит все простые числа в заданном диапазоне.
Ерунду написали, не будет работать.
Надо найденные простые числа сливать в массив и проверку проводить по нему.
Ну или хотя бы в цикле проверять делимость на все числа, меньше проверяемого. Это тупо, но без массива.