Как найти простые числа в паскале
Перейти к содержимому

Как найти простые числа в паскале

  • автор:

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

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

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

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

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

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

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

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

Пример выполнения программы:

56 31 18 15 7 101 0 Простых чисел: 3

Алгоритм нахождения простых чисел Pascal

Задача: найти все простые числа, не превышающие заданного. Ниже код. Не могли бы вы проверить нет ли там ошибки. Я не совсем уверен что он работает корректно. Буду благодарен.

Program Lab_4; var i, n, range : integer; Flag : boolean; Begin i := 0; n := 0; write('Введите диапазон: '); read(range); while i < range do Begin Flag := True; n := 0; i := i + 1; while n < i - 1 do Begin n := n + 1; if ((i mod n = 0) and (n >2)) or ((i mod 2 = 0) and (i <> 2)) then Flag := False; end; if Flag then writeln(i, ' - Простое число!'); end; end. 

Отслеживать
Pavel Durmanov
задан 13 мар 2017 в 16:18
Pavel Durmanov Pavel Durmanov
5,756 3 3 золотых знака 23 23 серебряных знака 44 44 бронзовых знака
Ну попробуйте поискать числа больше 2^128 и посмотрите.
13 мар 2017 в 16:20
Боюсь, они не влезут в integer.
13 мар 2017 в 16:24
Я уже это заметил(
13 мар 2017 в 16:24
Проверять делимость достаточно до квадратного корня, округлённого вниз.
13 мар 2017 в 16:26

. и только на простые числа. Не далее как сегодня уже одну программу пришлось писать. Взгляните, может, и поможет — правда, не на Pascal’е писано.

13 мар 2017 в 16:37

5 ответов 5

Сортировка: Сброс на вариант по умолчанию

Иногда бывает гораздо проще код просто переписать. Тогда повысится его читабельность.

Зачем Вы используете цикл while когда здесь нужен for , я не понял. Ну и как правильно заметили, проверять делимость нужно не до самого числа, а до его квадратного корня.

program Lab_4; var i, n, range : integer; Flag : boolean; begin write('Введите диапазон: '); read(range); for i := 2 to range do begin Flag := True; for n := 2 to Trunc(Sqrt(i)) do begin Flag := i mod n <> 0; if not Flag then break; end; if Flag then writeln(i, ' - Простое число!'); end; end. 

Как найти простые числа в паскале

По закону распределения простых чисел ищите границу.
А потом запускаете решето Эратосфена (линейное)
Или сразу в решето кинуть большую верхнюю границу

Регистрация: 17.11.2010
Сообщений: 18,922
массив констант в программе с простыми числами. Самый быстрый способ

Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
Поиск простого числа с номером 1’000’000. Переделайте под себя.
Это FreePascal

 < Печать 1000000-го простого числа > program Eratosfen; const //номер искомого простого числа NPrime = 1000 * 1000; //верхняя граница рассматриваемых кандидатов в простые числа Nmax = round(1.2 * NPrime * ln(NPrime)); type TVector = packed array [2..Nmax] of boolean; var PrimeCandidate, Step, j, Count: QWord; Sieve: TVector; begin (* PrimeCandidate := 2; while PrimeCandidate = j) do begin j := j + PrimeCandidate; Sieve[j] := False; end; Inc(Count); if Count = NPrime then break; end; case PrimeCandidate of 2: PrimeCandidate := 3; 3: PrimeCandidate := 5; else begin PrimeCandidate := PrimeCandidate + Step; Step := Step xor $6; end end; end; writeln('Max prime candidate = ', Nmax); writeln('Last prime = ', PrimeCandidate); writeln('Count = ', Count); end.

Пользователь
Регистрация: 24.04.2012
Сообщений: 68
А как такое решение, подойдет?

var i,j,a,c:integer; begin for i:=1 to 1000 do begin c:=0; for j:=1 to i do begin a:=i mod j; if i mod j=0 then inc(c); end; if c=2 then writeln(i); end; end.

Регистрация: 09.01.2008
Сообщений: 26,229

gromdel, нет.

во-первых, это КРАЙНЕ неэффективно (вы посчитайте, сколько делителей у числа 900, например), зачем крутить цикл, если уже понятно, что число не простое, зачем цикл до i, когда все делители расположены до sqrt(i) и т.д.

во-вторых, нужно найти 10000 простых чисел, а не найти простые числа в диапазоне от 1 до 1000! Разницу улавливаете? Вот Ваш код сколько простых чисел найдёт?
явно меньше 300

Serge_Bliznykov
Посмотреть профиль
Найти ещё сообщения от Serge_Bliznykov

Как найти простые числа в паскале

1. Найти количество простых чисел в интервале [10, 1000].

    del — делители;
    kd — количество делителей;
    k — количество простых чисел>
    if ch mod del=0 then inc(kd);

Наверх
Блок-схема

2. Найти простые числа в заданном интервале.

Ответ:
a=1
b=10
2 3 5 7

    ch — проверяемые числа;
    del — делители;
    kd — количество делителей;
    k — количество простых чисел>
    write(‘a=’); readln(a);
    write(‘b=’); readln(b);
    k:=0;
    for ch:=a to b do

      begin
      kd:=0;
      for del:=1 to ch do

        if ch mod del=0 then inc(kd);

      Наверх
      Блок-схема

      3. Найти двадцатое простое число.

      program prost_03;
      uses crt;
      var ch, del, kd, k : integer;

        del — делители;
        kd — количество делителей;
        k — счетчик простых чисел>

      Наверх
      Блок-схема

      4. Найти удвоенное десятое простое число.

      Ответ: k=10, ch=29, ch*2=58

      program prost_04;
      uses crt;
      var del, kd, k, ch:integer;

        del — делители;
        kd — количество делителей;
        k — счетчик простых чисел>
        begin
        ch:=ch+1; kd:=0;
        for del:=1 to ch do

          if ch mod del=0 then inc(kd);

        Наверх
        Блок-схема

        5.(1) Найти все простые двузначные числа, заканчивающиеся на цифру 3.

        Ответ: 13, 23, 43, 53, 73, 83

          clrscr;
          for ch:=10 to 99 do

            begin
            kd:=0;
            for del:=1 to ch do

              if ch mod del=0 then inc (kd);

            Наверх
            Блок-схема

            5.(2) Найти все простые двузначные числа, заканчивающиеся на цифру 3.

            Ответ: 13, 23, 43, 53, 73, 83

              for k:=1 to 9 do

                begin
                kd:=0;
                ch:=k*10+3;
                for del:=1 to ch-1 do

                  if ch mod del=0 then inc(kd);

                Наверх
                Блок-схема

                6. С клавиатуры вводятся 5 чисел. Найти количество простых, трехзначных

                Ответ может быт такой: 12, 13, 131, 131, 131 kch=3.

                  ch — число;
                  kd — количество делителей;
                  del — делители;
                  kol — количество чисел>
                  begin
                  readln(ch);
                  kd:=0;
                  for del:=1 to ch do

                    if ch mod del =0 then inc(kd);

                  Наверх
                  Блок-схема

                  7. Найти первое простое число, сумма цифр которого больше 10.
                  Ответ: 29

                    num — дубликат числа;
                    kd -количество делителей;
                    del — делитель;
                    c — цифра числа;
                    sum — сумма цифр числа>
                    if num mod del=0 then inc (kd);
                    begin
                    c:= num mod 10;
                    num:=num div 10;
                    sum:=sum+c
                    end;

                  Наверх
                  Блок-схема

                  8. С клавиатуры вводятся 5 чисел. Найти количество простых чисел, сумма цифр которых меньше 10.

                  Ответ может быть такой: 3, 3, 3, 3, 6 kch = 4

                  Наверх
                  Блок-схема

                  9. Найти первое простое число, сумма цифр которого больше 8, а произведение цифр меньше 10.

                    ch1 — дубликат числа ch для нахождения суммы и произведения его цифр;
                    del — делители;
                    kd — количество делителей;
                    c — цифры;
                    S — сумма цифр числа ch;
                    P — произведение цифр числа ch>

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *