Прайм-тест, 2-значные числа

Question

Я хочу напечатать все простые числа длиной 2 цифры. Вот мой код:

    for(int input = 11; input <= 99; input += 2){
        for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){
            if(input%x != 0){
                System.out.println(input);
                break;
            }else{
                break;
            }
        }
    }

Проблема в том, что он печатает числа типа 35 или 49, которые не являются простыми числами.

Answer 1

Ваш тест на первичность неверен.Вы прекращаете проверять число (input), как только вы обнаружите делитель, на который input не делится.

Это не определение простого числа - вам нужно проверить, что число inputне делится на любых делителей меньше его - другими словами, вам нужно проверить все значения x, прежде чем вы сможете объявить число простым числом.

Вы можете выйти изцикл, который проверяет input % x != 0, когда input делится на x, но не когда он не делится - вам нужно продолжать проверять, когда это условие истинно!

Answer 2

Мне всегда нравятся вопросы, где самый короткий и очевидный ответ - просто жестко закодировать вывод:

System.out.println("11\n13\n17\n19\n23\n29\n31\n37\n41\n43" +
   "\n47\n53\n59\n61\n67\n71\n73\n79\n83\n89\n97");

Answer 3

Чтобы найти простое число, вам не нужно проверять каждые числа под ним до его квадратного корня;вам просто нужно проверить все остальные простые числа под ним.Вот демонстрация:

ArrayList<Integer> primes = new ArrayList<Integer>(); // hold every other prime numbers that we find
boolean isPrime;

// add first base prime number
primes.add(2);

for (int x = 3; x < max; x+=2) {  // start from 3 and skip multiples of 2
    isPrime = true;  // prove it's not prime
    for (Integer i : primes) {
        if (x % i == 0) {
            isPrime = false; // x is divisible by a prime number... 
            break; // exit loop, we proved it's not a prime
        }
    }
    if (isPrime) {
        if (x >= 10) {
            System.out.println(x);  // print only two digits prime numbers
        }
        primes.add(x);  // add x to our prime our number list for future checks
    }
}

** EDIT **

Еще более гибкая и многократно используемая реализация в статическом методе (не оптимизирована для вывода больших простых чисел):

public static List<Integer> findPrimes(int min, int max) {
    LinkedList<Integer> primes = new LinkedList<Integer>();
    boolean isPrime;
    double square;

    // add first base prime number
    primes.add(2);

    for (int x = 3; x < max; x+=2) {  // start from 3 and skip multiples of 2

        isPrime = true;  // prove it's not prime
        square = Math.sqrt(x);
        for (Integer i : primes) {
            isPrime = x % i != 0;  // x is not prime if it is divisible by i
            if (!isPrime || i > square) { 
                break;
            }
        }
        if (isPrime) {
            primes.add(x);  // add x to our prime numbers
        }
    }

    // remove all numbers below min
    while (!primes.isEmpty() && primes.getFirst() < min) {
        primes.removeFirst();
    }

    return primes;
}

Использование метода:

List<Integer> primes = findPrimes(10, 100);
System.out.println("Listing " + primes.size() + " prime numbers");
for (Integer prime : primes) {
    System.out.println(prime);
}

Answer 4

Проблема в этом блоке:

if(input%x != 0)
{
System.out.println(input);
break;
}

Он выведет «input», если он не делится на текущее значение «x», но может делиться на следующие значения «x»,В этом случае «ввод» не является простым, но он печатается.

Правильный код:

boolean flag;
for(int input = 11; input <= 99; input += 2)
{
        flag = true;
        for(int x = 2; x < (int)Math.sqrt(input) + 1; x++)
        {
            if(input%x == 0)
            {
                flag = false;
                break;
            }
        }
        if(flag == true)
            System.out.println(input);
}

Answer 5

Википедия дает хороший алгоритм для поиска простых чисел.В нем также перечислены их число до 100.

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

Answer 6

Это работает.Вы можете увидеть вывод здесь .

public class Main {

public static void main(String[] args) {
for(int input = 11; input <= 99; input += 2){
    boolean found = false;
    for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){
        if(input%x == 0){
            found = true;
            break;
        }

    }
    if(!found) {
            System.out.println(input);
    }
}
}
}

Answer 7

Вы печатаете все нечетные числа.Вы всегда выходите из цикла, поэтому x никогда не превышает 2.

if(input%x != 0){
    System.out.println(input);
    break;  // <<-- break here
}else{
    break;  // <<-- and break here
}

Также тщательно продумайте определение простого числа:

• Если any проверяемых вами чисел является точным делителем, число не простое.
• Если все проверяемых вами чисел не являются точными делителями, то число простое.

Вы должны выйти из цикла, только если вы нашли делитель.Если вы еще не нашли, вам нужно продолжать, пока вы не проверили все возможности.И вы не должны ничего печатать, пока не закончите цикл и не узнаете результат.

Answer 8

for(int input = 11; input <= 99; input += 2){
    int found = 0;
    for(int x = 2; x < (int)Math.sqrt(input) + 1; x++)
        if(input%x == 0){
            found = 1;
            break;
        }
    if(found == 0)
        System.out.println(input);

}

это должно сделать работу

Answer 9

Да, потому что он распечатывает все случаи, когда обнаружен не фактор. Вам нужно ТОЛЬКО распечатать случаи, когда факторы не могут быть найдены.