Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.77/22: Рейтинг темы: голосов - 22, средняя оценка - 4.77
Mariasha
0 / 0 / 0
Регистрация: 31.08.2013
Сообщений: 26
1

Алгоритм, который устанавливает – является ли число простым

01.04.2015, 14:27. Просмотров 4516. Ответов 20
Метки нет (Все метки)

5. Алгоритм, который устанавливает – является ли число N
простым. Число называется простым, если оно делится нацело
без остатка только на себя и на 1.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2015, 14:27
Ответы с готовыми решениями:

Является ли число простым
Определить является ли число простым. Состав те функцию определяющую простое...

Определить, является ли число простым
While22. Дано целое число N (> 1). Если оно является простым, то есть не имеет...

Выяснить является ли число простым
Дано целое число N. Определить является ли оно простым. Как найти делители...

является ли заданное натуральное число n простым
Составить рекурсивную программу-функцию проверяющую, является ли заданное...

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

20
Joy
Эксперт Pascal/Delphi
2169 / 1197 / 1437
Регистрация: 29.08.2014
Сообщений: 4,387
01.04.2015, 18:36 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
  n,i,k:longint;
  p:boolean;
begin
  write('n=');
  readln(n);
  if n=0 then writeln(' это ноль!') else begin
    p:=true;
    for i:=2 to n div 2 do if n mod i=0 then begin p:=false;break;end;
    write(n,'-число ');
    if p then writeln('простое') else writeln ('не простое');
  end;
end.
1
kukuryza
15 / 15 / 12
Регистрация: 01.02.2014
Сообщений: 62
01.04.2015, 18:36 3
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
  n,i,k:longint;
  begin
  writeln('введите число n');
  readln(n);
  k:=0;
  for i:=2 to n do begin
  if n mod i =0 then k:=k+1;
  if k>0 then break;
  end;
  if i=n then writeln('число является простым')
  else writeln('число не является простым')
  end.
1
Joy
Эксперт Pascal/Delphi
2169 / 1197 / 1437
Регистрация: 29.08.2014
Сообщений: 4,387
01.04.2015, 19:27 4
kukuryza, есть ляп:
введите число n
1
число не является простым
1
kukuryza
15 / 15 / 12
Регистрация: 01.02.2014
Сообщений: 62
01.04.2015, 19:57 5
поставить условие что если введено 1 то простое
0
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
02.04.2015, 00:11 6
Joy, по определению, число 1 простым не является.

Просто́е число́ — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя.
1
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4021 / 2647 / 2126
Регистрация: 22.11.2013
Сообщений: 7,433
02.04.2015, 08:29 7
Joy,
Pascal
9
    for i:=2 to Trunc(sqrt(n)) do
Для непростых значения не имеет, у них выход по Break будет всё равно не позже, а по простым будет меньше бегать, делители ведь парные, если до кв.корня не встретился делитель, то после его не будет уже гарантированно.

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

Добавлено через 2 минуты
А можно втихаря составлять табличку простых и проверять делимость только на них, будет еще быстрее. Но алгоритм выйдет несколько запутаннее.
3
Joy
Эксперт Pascal/Delphi
2169 / 1197 / 1437
Регистрация: 29.08.2014
Сообщений: 4,387
02.04.2015, 08:56 8
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var
  n:longint;
function isp(n:longint):boolean;
var
  i,k:longint;
  p:boolean;
begin
    p:=true;
    if n>3 then begin
    i:=3;
    k:=round(sqrt(n));
    if odd(n) then
    repeat
      if n mod i=0 then p:=false;
      inc(i,2);
    until (i>=k) or (not p) else p:=false;
    end;
   isp:=p;
end;
begin
  repeat
    write('n=');
    readln(n);
  until n>1;
    write(n,' - ');
    if isp(n) then writeln('простое') else writeln ('составное');
end.
1
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4021 / 2647 / 2126
Регистрация: 22.11.2013
Сообщений: 7,433
02.04.2015, 10:18 9
Вариация на тему:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const
  NY: array [Boolean] of String[9] = ('составное', 'простое');
var
  n: Longint;
function isp(n: Longint): Boolean;
var
  i,k: Longint;
  p: Boolean;
begin
  p:=n>1; { натуральные больше 1 }
  if n>3 then begin
    if Odd(n) then begin
      i:=3; k:=Trunc(sqrt(n));
      repeat
        if n mod i=0 then p:=false;
        Inc(i,2);
      until not p or (i>=k)
    end else p:=False;
  end;
  isp:=p;
end;
begin
  repeat
    write('n='); readln(n);
  until n>1;
  WriteLn(n,' - ',NY[isp(n)]);
end.
1
Новичок
Модератор
1510 / 978 / 465
Регистрация: 17.07.2012
Сообщений: 4,966
Завершенные тесты: 3
02.04.2015, 15:18 10
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
function isPrime(x:LongInt):Boolean;
var i:Integer;
begin
isPrime:=False;
if (not odd(x) and (x<>2)) or (x=1) then Exit;
i:=3;
while i<=Round(sqrt(x)) do
 begin
  if x mod i=0 then Exit;
  inc(i,2);//Проверяем только нечётные делители
 end;
isPrime:=true;
end;
0
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
02.04.2015, 18:01 11
bormant, Joy, "немножко" соптимизировать можно:
Pascal
12
    if ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0) then {...}
1
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4021 / 2647 / 2126
Регистрация: 22.11.2013
Сообщений: 7,433
02.04.2015, 18:42 12
Новичок,
не надо так писать:
Pascal
1
while i<=Round(sqrt(x)) do
Во 1-х, sqrt() операция небыстрая, незачем ее на каждом шаге вычислять, это не for .. do, где начальное и конечное значения вычисляются один раз перед циклом, не нужно экономить переменную.
Во 2-х, незачем Round() (возможен лишний шаг), когда достаточно Trunc().
1
Joy
Эксперт Pascal/Delphi
2169 / 1197 / 1437
Регистрация: 29.08.2014
Сообщений: 4,387
03.04.2015, 03:04 13
Cyborg Drone, хорошая формула, спасибо, не знал
0
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
08.04.2015, 21:57 14
Формула, однако, особенного выигрыша не даёт. На её основе у меня вот что нарисовалось:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function IsPrime(n: longint): boolean;
var i, p: longint;
begin
  IsPrime := (n = 2) or (n = 3);
  if (n >= 5) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0)
    then begin
      IsPrime := true;
      i := 5;
      p := trunc(sqrt(n));
      while i <= p do
        begin
          if n mod i = 0
            then begin
              IsPrime := false;
              break
            end;
          inc(i, 2);
          if i mod 3 = 0 then inc(i, 2)
        end
    end
end;
Вот и вопрос: может, не нужен этот i mod 3... Лишний раз mod... Может, пусть себе это лишнее n mod i выполнится... Да, луше убрать, быстрее будет.

Добавлено через 14 минут
Хотя... При обработке массива чисел будут исключаться n < 25 и четыре числа из шести... Не так уж и плохо. Ну что, люди, раскритикуйте меня, что ли, а то у меня, подозреваю, ложное, самомнение что-то зашевелилось...
0
ФедосеевПавел
Модератор
3761 / 2113 / 862
Регистрация: 01.02.2015
Сообщений: 7,019
08.04.2015, 23:25 15
Может быть проверить делимость тестируемого числа на 2,3,5, а потом делать приращение не inc(i,2) а
Pascal
1
2
3
4
5
6
7
  delta:=2;
  while () do
  begin
............
    delta:=delta xor $06; - смена шага - то 2 то 4
    inc(i, delta);
  end;
А вообще - в Wikipedia присутствует описание нескольких алгоритмов (в том числе и вероятностных) проверки на простоту - они чуть сложнее решета Эратосфена.
1
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
09.04.2015, 03:01 16
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
проверить делимость тестируемого числа на 2,3,5
А на 5... Зачем?
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
в Wikipedia
Читал когда-то давно. Ну, вероятностные алгоитмы для сравнительно малых чисел неэффективны, а для больших всё равно требуют дополнительной проверки на простоту числа, на то они и вероятностные. А решёта различные служат не для проверки простоты числа, а для нахождения всех простых чисел, меньших наперёд заданного числа. И не такие уж они простые, все эти Эратосфены и Аткины, всем им требуется немножко памяти. Ну да ладно. Вернёмся к нашим баранам.

У меня там тоже 2-4, только не столь эффективное, как У Вас. Я всё думал, как произвести инкремент числа то на 2, то на 4, исходя из самого i, ничего толкового не придумал, кроме того, что числа, которые требуется исключить, делятся на 3 нацело: 5, 7, 9, 11, 13, 15, 17, 19, 21, 23... и до Вашего варианта не дошёл, хотя, про xor мысль мелькала. Однако, вопрос об эффективности алгоритма с перебором делителей: фактически, 2-4 исключает из рассмотрения каждое третье нечётное число. Ну и, что имеем с гуся на каждые три числа?

3 * mod + 3 * inc = 3 * idiv + 3 * add = 3 * 4 + 3 * 1 = 15 - если делить на каждое нечётное;
2 * mod + 2 * inc + 2 * xor = 2 * idiv + 2 * add + 2* xor = 2 * 4 + 2 * 1 + 2 * 1 = 12 - Ваш вариант.

Ну что, несколько поэффективней будет... Для ABC не подходит, но у меня он всё равно не стоит и я его ненавижу. Спасибо.
1
ФедосеевПавел
Модератор
3761 / 2113 / 862
Регистрация: 01.02.2015
Сообщений: 7,019
09.04.2015, 21:07 17
Да, приращение небольшое - всего 33%...
Но программа с таким алгоритмом уже интереснее и оригинальнее перебора всех чисел.

Формулу для описания простых чисел я знал ещё со школы, но как ею воспользоваться увидел только вчера

Спасибо!
0
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
09.04.2015, 22:28 18
Ну и, окончательный вариант, мало ли, вдруг кому два фрагмента в один ну никак не сообразится:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function IsPrime(n: longint): boolean;
var i, sqrtn, delta: longint;
begin
  IsPrime := (n = 2) or (n = 3);
  if (n >= 5) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0)
    then begin
      IsPrime := true;
      i := 5;
      delta := 2;
      sqrtn := trunc(sqrt(n));
      while i <= sqrtn do
        begin
          if n mod i = 0
            then begin
              IsPrime := false;
              break
            end;
          inc(i, delta);
          delta := delta xor 6 {смена шага - то 2 то 4}
        end
    end
end;
0
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4021 / 2647 / 2126
Регистрация: 22.11.2013
Сообщений: 7,433
10.04.2015, 00:10 19
Лучший ответ Сообщение было отмечено Cyborg Drone как решение

Решение

Cyborg Drone,
На мой вкус, чуть поправил бы.
Если положить до проверки IsPrime:=False, то по нахождению делителя можно сразу выйти по Exit, а если дожили до завершения цикла -- присвоить IsPrime True:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function IsPrime(n: Longint): Boolean;
var i, sqrtn, delta: Word;
begin
  if (n >= 5) and ((n - 1) mod 6 = 0) or ((n + 1) mod 6 = 0) then begin
    i := 5;
    delta := 2;
    sqrtn := Trunc(sqrt(n));
    IsPrime := False;
    while i <= sqrtn do begin
      if n mod i = 0 then Exit;
      Inc(i, delta);
      delta := delta xor 6; {смена шага, то 2, то 4}
    end;
    IsPrime := True;
  end else
    IsPrime := (n = 2) or (n = 3);
end;
2
Cyborg Drone
Модератор
5398 / 3202 / 2450
Регистрация: 17.08.2012
Сообщений: 10,274
10.04.2015, 01:41 20
Да, и на мой вкус так лучше.
0
10.04.2015, 01:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2015, 01:41

Является целое число, введенное пользователем простым.
Помогите решить,плиз!!!(((( 1.Написать программу, которая проверяет,...

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

Является ли введенное пользователем натуральное число простым
Напишите программу,определяющую,является ли введенное пользователем натуральное...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru