Определить количество простых чисел

Задача

Вводятся целые числа до первого числа, которое меньше двух. Определить, сколько простых чисел было введено.

Решение

Простые числа - это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2. Число 2 является простым, хотя делится на 2, однако это деление – деление само на себя.

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

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

Описание переменных: 

  • count - счетчик простых чисел;
  • number - очередное введенное число.

Алгоритм решения задачи: 

Пока введенное число больше 1, проверять его на простоту по следующему алгоритму:

  1. Если число делится на любой делитель от 2 до квадратного корня из себя, то оно составное.
  2. Если число так и не разделилось ни на один из перебранных делителей, то оно простое, следовательно, увеличиваем счетчик простых чисел.
var
    number, count, i: integer;
    flag: boolean;
 
begin
    count := 0;
 
    write('Number: ');
    readln(number);
 
    while number > 1 do begin
        flag := true;
 
        for i:=2 to round(sqrt(number)) do
            if number mod i = 0 then
                flag := false;
 
        if flag then
            count := count + 1;
 
        write('Number: ');
        readln(number);
    end;
 
    writeln(count,' prime numbers');
end.

Комментарии

Составить программу для проверки утверждения: “Результатами вычислений по формуле x2 + x + 17 при 0 ≤ x ≤ 15 являются простые числа. Все результаты вывести на экран.

var
    x, i: byte;
    y: word;
    f,h: boolean;
begin
    h := true;
    for x:=0 to 15 do begin
        y := x*x + x + 17;
        f:=true;
        for i:=2 to y div 2 do
            if y mod i = 0 then
                f:=false;
        if f = true then 
            writeln('x=',x,'; y=',y,'- простое число')
        else begin
            writeln('x=',x,'; y=',y,'- сложное число');
            h := false;
        end;
    end;
    if h = true then 
        writeln('Утверждение верно. Все числа простые')
    else
        writeln('Утверждение не верно. Есть сложные');
end.