Простое число Логика, n/2 условие в цикле

Question

Следующий код для простого числа. Я хочу знать, почему мы используем i<=n/2 состояние в цикле.

Программа C:

#include <stdio.h>
int main()
{
int n, i, flag = 0;

printf("Enter a positive integer: ");
scanf("%d",&n);

for(i=2; i<=n/2; ++i)
{
    // condition for nonprime number
    if(n%i==0)
    {
        flag=1;
        break;
    }
}

if (flag==0)
    printf("%d is a prime number.",n);
else
    printf("%d is not a prime number.",n);

return 0;
}

Answer 1

Хотя это программа на Си. Но логика простых чисел для C и Java будет одинаковой

простое число
Каждое натуральное число, которое делится только на 1 и само является простым. Также 2 - это первое простое число.

Например, мы хотим проверить, является ли число 100 простым числом или нет. мы можем сделать пробное деление, чтобы проверить простоту 100.

Давайте посмотрим на все делители 100:

2, 4, 5, 10, 20, 25, 50

Здесь мы видим, что наибольшим фактором является 100/2 = 50. Это верно для всех n: все делители меньше или равны n / 2.

Так что здесь условие i<=n/2 является правильным. Так как нам нужно тестировать делители только до n / 2.

Пожалуйста, проверьте ссылку Wiki для более подробной информации https://en.wikipedia.org/wiki/Primality_test

Второй пример

Аналогично, для 11 вы должны проверить все целые числа меньше 5,5, то есть 1, 2, 3, 4 и 5.

Чтобы найти число простое, почему проверка до п / 2 лучше. В чем причина избегания чисел во второй половине дня?

Answer 2

Наибольшее значение для любого числа n должно быть <= n/2, поэтому нет необходимости проверять большие числа