Как определить простое число
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя — единицу и самого себя.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
А теперь перейдём к задаче. По сути нам нужна программа, определяющая простые числа. А уж перебрать элементы массива в цикле и проверить их значения — это дело техники. Заодно мы можем не только подсчитать, но и вывести на экран простые числа массива.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Саму функцию здесь приводить не буду — посмотрите её в примерах программ.
Turbo pascal и Простые числа
Простое число — натуральное число, которое делится только на единицу и само на себя. Ряд простых чисел: 2, 3, 5, 7, 11. Самым большим из известных простых чисел является 2 43112609 -1 (Число Мерсенна).
Как найти простые числа в Паскале?
Найти простые числа в паскале можно несколькими способами. Однако, все способы их нахождения основываются на переборе чисел. Самым простым алгоритмом нахождения простых чисел в pascal является организация цикла от 3 до заданного верхнего предела, где перебираемые числа делятся на все значения от 2 до N-1. Само собой, что единица и само число не считается в качестве делителя.
На языке Паскаль делать алгоритм быстрее можно если делить все числа от 2 до корня из N включительно
while (i mod j <> 0) and (j <= lim) do inc( j );
if (j > lim) then write( i,’ ‘ );
Усовершенствовать алгоритм можно посредством деления цифр, оканчивающихся только на 1, 3, 7 или 9. Числа, оканчивающиеся на 0 и 5 не могут являться простыми, также как и четные числа.
Простые числа — Нахождение всех простых чисел в Паскале от 1 до N
Простые числа и их квадраты — Вывод в Turbo Pascal простых чисел и их квадратов
Алгоритм нахождения простых чисел Pascal
Задача: найти все простые числа, не превышающие заданного. Ниже код. Не могли бы вы проверить нет ли там ошибки. Я не совсем уверен что он работает корректно. Буду благодарен.
Иногда бывает гораздо проще код просто переписать. Тогда повысится его читабельность.
Зачем Вы используете цикл while когда здесь нужен for , я не понял. Ну и как правильно заметили, проверять делимость нужно не до самого числа, а до его квадратного корня.
Вот, посмотрите. Что-то вроде такого должно быть.
Вы можете проверить свою программу на наличие ошибок в автоматизированной системе. Например, здесь. Правда, ввод/вывод программы понадобится адаптировать для тестирующей системы, но это просто.
Простое ли число (Паскаль)?
Чтобы определить, является ли число N простым на Паскале, следует последовательно делить N на числа в промежутке от 2 до N/2. Если в процессе такого деления хотя бы один раз получится так, что остаток от деления будет составлять 0, значит число имеет помимо самого себя еще какой-то делитель. А следовательно число не является простым. Вот так легко определить является ли число простым.
program ex37;
uses crt;
var n, i,f, z: integer;
begin
clrscr;
write(‘Введите натуральное число n= ‘);
readln(n);
f:=0; <Начальное значение флага>
i:=2; <Начальное значение делителя>
z:=n div 2;
while (i<=z) and (f=0) do
begin
if n mod i =0 then f:=1;
i:=i+1;
end;
if f=1 then
writeln(‘Число не простое’)
else
writeln(‘Число простое’);
readln;
end.