Определение первичности [Тьюринга]

Question

put "enter a number to determine if it is or is not prime"
get primenum
% for i : 1 .. primenum by 1
% end for
if (primenum / primenum) = 1 or primenum / 1 = 0 then
    put primenum, " is a prime number"
else
    put primenum, " is not a prime number"
end if

Выходные данные говорят, что 12 - это простое число, мы знаем, что это неправильно, поэтому ...
Что не так с моим кодом, и как я могу это исправить?

Answer 1

Ну, я не знаю этот язык, но он выглядит довольно легко читаемым. Ваша первая проблема - эта строка:

if (primenum / primenum) = 1 or primenum / 1 = 0 then

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

Давайте вспомним определение простого числа. Натуральное число n является простым, если оно имеет ровно два различных делителя натуральных чисел. Это означает, что для проверки и определения простоты n необходимо проверить, что нет других делителей n, кроме 1 и n (обратите внимание, что неявно n не может быть равно 1 в противном случае его единственными делителями являются 1 и 1, которые не различаются). Для этого просто рассмотрите все возможные числа, которые могут быть делителями n, исключая 1 и n, и проверьте, делит ли любое из них n. Это означает, что мы просто выполняем цикл от 2 до n - 1, проверяя, равномерно ли любое из этих чисел делится на n. Натуральные числа в диапазоне от 2 до n - 1 являются единственно возможными числами, которые могут сделать недействительным n от простого числа.

Таким образом, наиболее наивный способ реализации теста на то, является ли число простым, заключается в следующем. Принять в качестве ввода число n. Затем проверьте, если n меньше 2. Если это не может быть простым числом. Затем выполните цикл от 2 до n - 1; вызовите переменную цикла k. Проверьте, нет ли равномерного деления k в 2 на n - 1 n (if n mod k = 0). Если есть такой k, то n не может быть простым, и вы можете выйти из цикла. В противном случае, если цикл завершается без прерывания, то n является простым. Итак, в псевдокоде

integer n
get n
boolean flag
if n < 2
    flag = false
else
    flag = true
    for k = 2 to n - 1
        if n mod k = 0 
            flag = false
            break
if flag
    print "prime"
else
    print "not prime"

Теперь, только один небольшой комментарий о вашем коде. Не называйте ввод primenum. Читатель вашего кода может подумать, что primenum на самом деле простое число, потому что вы назвали его так. Такое имя, как valueToTest, было бы здесь более предпочтительным.

Answer 2

Ваш код ... не имеет большого смысла.

% for i : 1 .. primenum by 1
% end for

Wooh. Пустой цикл Ничего не делает, кроме циклов записи часов.

if (primenum mod primenum) = 0

Всегда будет true.

Кроме того, вы ошиблись в своем состоянии. Если оно делится на что-либо (кроме себя и 1), то оно не простое.

Решение? Возможно, переписать его в psuedocode, а затем превратить в реальный код, вместо того, чтобы пытаться что-то взломать, совсем не понимая.

Answer 3

Определяющим свойством простого числа является не то, что оно делится на , делимое на 1 и на самого себя (все числа имеют эти свойства), а то, что оно не является делимым на что-либо еще.

Попробуйте работать оттуда.