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

Задача

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

Решение

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

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

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

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

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

Программа на языке Паскаль: 

 

var
    n,i,q: integer;
    f: boolean;
begin
    q:=0;
    write('Number: ');
    readln(n);
    while n > 1 do begin
        f:=true;
        for i:=2 to n div 2 do
            if n mod i = 0 then
                f:=false;
        if f then
            q:=q+1;
        write('Number: ');
        readln(n);
    end;
    writeln(q,' prime numbers');
readln;
end.

 

Тема

Циклы

Уровень

Простые задачи

Комментарии

Вместо for i:=2 to n div 2 лучше написать for i:=2 to round(sqrt(n)) Конечно, программа выдаст результат и так... Но для n=101 проверит 50 чисел вместо 10.

И стоит выделить блок "поиск простого числа" . Либо в функцию, либо комментарием - ведь программу будут читать неспециалисты :)

А если n=2? Программа выдает 0 простых чисел. Нужно или переформулировать задачу "до первого числа, которое не больше двух", или исправить код.

Составить программу для проверки утверждения: “Результатами вычислений по формуле 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.

Добавить комментарий