Turbo pascal и Простые числа
Простое число — натуральное число, которое делится только на единицу и само на себя. Ряд простых чисел: 2, 3, 5, 7, 11. Самым большим из известных простых чисел является 2 43112609 -1 (Число Мерсенна).
Как найти простые числа в Паскале?
Найти простые числа в паскале можно несколькими способами. Однако, все способы их нахождения основываются на переборе чисел. Самым простым алгоритмом нахождения простых чисел в pascal является организация цикла от 3 до заданного верхнего предела, где перебираемые числа делятся на все значения от 2 до N-1. Само собой, что единица и само число не считается в качестве делителя.
На языке Паскаль делать алгоритм быстрее можно если делить все числа от 2 до корня из N включительно
while (i mod j <> 0) and (j
if (j > lim) then write( i,’ ‘ );
Усовершенствовать алгоритм можно посредством деления цифр, оканчивающихся только на 1, 3, 7 или 9. Числа, оканчивающиеся на 0 и 5 не могут являться простыми, также как и четные числа.
Простые числа — Нахождение всех простых чисел в Паскале от 1 до N
Простые числа и их квадраты — Вывод в Turbo Pascal простых чисел и их квадратов
Простые числа-близнецы — Вывод простых чисел-близнецов
| Карта сайта |
| С информацией по модернизации сайта bpascal.ru, техническим неисправностям, а также вопросами по размещению рекламы обращаться по адресу ShekhovtsovY@yandex.ru. Ваше заявление будет рассмотрено в кратчайшие сроки. |
Определить количество простых чисел
С клавиатуры вводятся целые числа до первого числа, которое меньше двух. Написать программу, которая определяет сколько простых чисел было введено.
Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.
Перебор делителей – это алгоритм, применяемый для определения, является ли натуральное число простым, или оно является сложным, то есть составным. Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа.
Если хотя бы один делитель делит исследуемое число без остатка, значит это число является составным. Если ни одного такого делителя не находится, то число признается простым.
- count — счетчик простых чисел;
- number — очередное введенное число.
Пока введенное число больше 1, проверять его на простоту по следующему алгоритму:
- Если число делится на любой делитель от 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Как найти простые числа в паскале
По закону распределения простых чисел ищите границу.
А потом запускаете решето Эратосфена (линейное)
Или сразу в решето кинуть большую верхнюю границу
Регистрация: 17.11.2010
Сообщений: 19,042
массив констант в программе с простыми числами. Самый быстрый способ
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Форумчанин
Регистрация: 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,238
gromdel, нет.
во-первых, это КРАЙНЕ неэффективно (вы посчитайте, сколько делителей у числа 900, например), зачем крутить цикл, если уже понятно, что число не простое, зачем цикл до i, когда все делители расположены до sqrt(i) и т.д.
во-вторых, нужно найти 10000 простых чисел, а не найти простые числа в диапазоне от 1 до 1000! Разницу улавливаете? Вот Ваш код сколько простых чисел найдёт?
явно меньше 300
| Serge_Bliznykov |
| Посмотреть профиль |
| Найти ещё сообщения от Serge_Bliznykov |
Алгоритм нахождения простых чисел 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,746 3 3 золотых знака 22 22 серебряных знака 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.