1

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

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.
6
  • Ну попробуйте поискать числа больше 2^128 и посмотрите... 13 мар 2017 в 16:20
  • 1
    Боюсь, они не влезут в integer. 13 мар 2017 в 16:24
  • Я уже это заметил( 13 мар 2017 в 16:24
  • 1
    Проверять делимость достаточно до квадратного корня, округлённого вниз. 13 мар 2017 в 16:26
  • ... и только на простые числа. Не далее как сегодня уже одну программу пришлось писать. Взгляните, может, и поможет - правда, не на Pascal'е писано...
    – Harry
    13 мар 2017 в 16:37

5 ответов 5

3

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

Зачем Вы используете цикл 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.
1
  • Вы правы на счет цикла for. Я уже сделал этим способом. У меня задание сделать циклами: while, for, repeat. 13 мар 2017 в 16:48
2

Вот, посмотрите. Что-то вроде такого должно быть.

program Lab_4;

var
  i, n, range: integer;
  Flag: boolean;

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

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

2

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

  1. Просеивать только нечётные числа. Т.е. элемент решета a[m] должен содержать число m и соответствовать числу 2m+1.
  2. Исключить из массива все числа вида i+j+2ij, поскольку 2(i+j+2ij)+1 = (2i+1)(2j+1).
    Этого достаточно, поскольку все составные нечётные числа являются произведением нечётных чисел.
  3. Границы по меньшему индексу i определяются условием (2i+1)2 ∈ [3, 2M+1], где M - размерность массива a.
    Т.е. i ∈ [1, sqrt(2M+1) / 2 -1 ]
  4. Границы по большему индексу j определяются условием i+j+2ij ∈ [1, M].
    Т.е. j ∈ [1, (M-i) / (2i+1)].
  5. Перебор по i и j проводится с шагом 1.
  6. Значения m, полученные в результате отбора, следует пересчитать в простые числа по формуле p=2m+1.
4
  • Хотя по ссылке можно найти ответ на вопрос, лучше указать здесь самое главное, а ссылку приводить в качестве источника. Если страница, на которую ведет ссылка, будет изменена, ответ-ссылка может стать недействительным. - Из очереди проверок
    – cheops
    17 мар 2017 в 1:45
  • Вот честно, ничего интересного в статье нет. Автор сам в теме не разобрался... В комментариях инфа есть, но чтобы её понять нужно явно больше опыта иметь чем ответ на этот вопрос найти
    – pavel
    17 мар 2017 в 6:38
  • @cheops Спасибо, учёл. 17 мар 2017 в 15:23
  • @pavel Согласен, так и есть. А с другой стороны - на ruSO тема решета Эратосфена обкатана вдоль и поперёк. Хватит уже изобретать велосипеды, 17 мар 2017 в 15:28
-1

Данное решение может быть и длинное, но работает
UPD: обновлено по просьбе aleksandr barakin

program stack;
function simple(x:int64):boolean;
begin
    if((x=2)or(x=3)or(x=5)or(x=7)or((x mod 2<>0)and(x mod 3<>0)and(x mod 5<>0)and(x mod 7<>0))) then simple:=true
    else simple:=false;
end;
var i,n:int64;
begin
Write('N = '); ReadLn(n);
for i:=1 to n do 
    if(simple(i))then WriteLn(i,' - Простое число');
end.
5
  • 1
    добро пожаловать на stack overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 14 апр 2022 в 13:36
  • 1
    Интересно, с каких пор 9 стало простым числом. Ну и после 100 уже фактически не работает нормально.
    – insolor
    14 апр 2022 в 15:28
  • Ладно, недочет. А если убрать эту девятку, то все равно не работает?
    – No_name
    15 апр 2022 в 4:40
  • Это не решение.
    – MBo
    15 апр 2022 в 4:41
  • Это решение с очень ограниченной областью, где оно корректно работает, фактически от 2 до 120. От 121 и до 3569 есть 320 чисел, которые простыми не являются, но ваша функция их таковыми считает. На алгоритм нахождения простых чисел это явно не тянет.
    – insolor
    15 апр 2022 в 4:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.