Пример программы паскаль, которая находит все делители натурального числа и их сумму

Простое число – это натуральное число, которое делиться без остатка на себя и на единицу.

Метод для проверки, является ли число простым

Исходя из определения простоты числа, напишем метод для проверки.

Простое число должно удовлетворять условиям:

  • Быть больше единицы – условие проверим с помощью условного оператора if;
  • Делиться нацело только на один и на себя – в цикле проверим делиться ли N нацело на числа из диапазона от 2 до N-1.
public static bool IsPrimeNumber(uint n) {     var result = true;      if (n > 1)     {         for (var i = 2u; i < n; i++)         {             if (n % i == 0)             {                 result = false;                 break;             }         }     }     else     {         result = false;     }      return result; } 

Если число, которое передается в качестве аргумента метода, является простым, метод возвращает значение true и false в противном случае.

Использование метода для проверки числа N на простоту

Простые числа из диапазона от 0 до N

Используя метод для проверки, можем вывести на экран все простые числа из промежутка от 0 до N.

Программа позволяющая вывести простые числа из отрезка:

static void Main(string[] args) {     Console.Write("N = ");     var n = Convert.ToUInt32(Console.ReadLine());     Console.WriteLine("Простые числа из диапазона ({0}, {1})", 0, n);     for (var i = 0u; i < n; i++)     {         if (IsPrimeNumber(i))         {             Console.Write($"{i} ");         }     }      Console.ReadLine(); } 

Результат работы программы:

N первых простых чисел

После небольшой модификации программы, можем вывести необходимое количество простых чисел.

Программа позволяющая вывести на экран N первых простых чисел:

static void Main(string[] args) {     Console.Write("N = ");     var n = Convert.ToUInt32(Console.ReadLine());     Console.WriteLine("{0} первых простых чисел", n);     var count = 0u;     var i = 0u;     while (count < n)     {         if (IsPrimeNumber(i))         {             Console.Write(i);             if (count < n - 1)             {                 Console.Write(", ");             }             count++;         }         i++;     }               Console.ReadLine(); } 

Смотрите также:

Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23… Единица не является ни простым числом, ни составным.

Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).

Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).

Все натуральные числа считаются либо простыми, либо составными (кроме 1).

Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4… (нет ни дробей, ни 0, ни чисел ниже 0).

Зачастую множество простых чисел в математике обозначается буквой P.

Простые числа до 1000

2 3 5 7 11 13 17 19 23
29 31 37 41 43 47 53 59 61 67
71 73 79 83 89 97 101 103 107 109
113 127 131 137 139 149

151

157

163

167

173

179

181

191

193

197

199

211

223

227

229

233

239

241

251

257

263

269

271

277

281

283

293

307

311

313

317

331

337

347

349

353

359

367

373

379

383

389

397

401

409

419

421

431

433

439

443

449

457

461

463

467

479

487

491

499

503

509

521

523

541

547

557

563

569

571

577

587

593

599

601

607

613

617

619

631

641

643

647

653

659

661

673

677

683

691

701

709

719

727

733

739

743

751

757

761

769

773

787

797

809

811

821

823

827

829

839

853

857

859

863

877

881

883

887

907

911

919

929

937

941

947

953

967

971

977

983

991 997

Как определить, является ли число простым?

Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.

Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).

Более структурированный метод — это решето Эратосфена.

Решето Эратосфена

Это алгоритм поиска простых чисел. Для этого нужно:

  1. Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
  2. Вычеркнуть все числа, которые делятся на 2 (кроме 2);
  3. Вычеркнуть все числа, которые делятся на 3 (кроме 3);
  4. И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).

Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.

Взаимно простые числа

Это натуральные числа, у которых 1 — это единственный общий делитель. Например:

  • 14 (это 2 х 7) и 15 (это 3 х 5), единственный общий делитель — 1; если числа следуют одно за другим (как 13 и 12 либо 10 и 11), то они всегда будут взаимно простыми;
  • 7 (это 7 х 1) и 11 (это 11 х 1) — это два простых числа, а значит единственный общий делитель всегда будет только единица, простые числа всегда являются взаимно простыми;
  • или 30 и 48 не являются взаимно простыми, т. к. 6 х 5 = 30 и 6 х 8 = 48 и 6 — это наибольший общий делитель, т. е.: НОД (30; 48) = 6.

Число Мерсенна

Простое число Мерсенна — это простое число вида:

image

До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).

Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.

Почему 1 не является простым числом?

Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.

Почему 4 не является простым числом?

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

Самое большое простое число

21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:

image

Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).

Узнайте про Рациональные числа и Натуральные числа.

Определение:

Простое число — это натуральное число (>0), которое имеет не более двух различных делителей: 1 и само число. Натуральные числа, кроме 1, не относящиеся к простым числам, называются составными. Единица не является ни простым числом ,ни составным. Примеры простых чисел: 3,5,7,11,17 Возьмем, к примеру, число 3. 3 делится ,нацело, только на 1 и само на себя, следовательно число 3 является простым числом.Сообщить об ошибке

Смотрите также

Проценты Арифметические действия Решение дробей Площадь фигур Объем фигур
Простые и составные числа Решение уравнений Решение интегралов Решение функций Решение СЛУ

Опубликовано вкл 18.05.2021 — 19:10 Автор:  Гильманова Аделина, Шестиперова Виктория

Цель: изучение множества простых чисел.

Задачи:

1.Изучить свойства и особенности простых чисел.

2.Изучить методы для нахождения простых чисел (теория Чебышева).

3.Выяснить применение простых чисел.

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

2.Наблюдение, сравнение, анализ, обобщение и систематизация изученного материала.

Актуальность:

Простые числа с давних времен привлекают внимание математиков. Простые числа следует одно за другим по закону, который еще не найден. Но простые числа в математике играют важную роль. Из них с помощью умножения получаются все остальные числа. Хорошо было бы, если все простые числа можно было сосчитать! Но эта проблема до сих пор остается нерешенной. Как сказал Евклид: самого большого простого числа не существует.

Гипотеза:

Если эти числа называются «простыми», то все эти числа давно изучены и про них уже все известно.

Скачать:

Вложение Размер
proekt.docx 32.23 КБ

Предварительный просмотр:

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ «ЗАИНСКАЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №3»

 ЗАИНСКОГО МУНИЦИПАЛЬНОГО РАЙОНА

ЗАГАДКА ПРОСТЫХ ЧИСЕЛ

ПРОЕКТ

                                                                                                           Авторы:

                                                                                                ГильмановаАделина, 7 А класс

Шестипёрова Виктория, 7 А класс

                                                                                                           Научный руководитель:

                                                                                                           Хасметдинова А.А.

2021 г.

ОГЛАВЛЕНИЕ

  1. Введение
  2. Основная часть
  3. Заключение
  4. Список литературы

Введение

Цель: изучение множества простых чисел.

Задачи:

1.Изучить свойства и особенности простых чисел.

2.Изучить методы для нахождения простых чисел (теория Чебышева).

3.Выяснить применение простых чисел.

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

2.Наблюдение, сравнение, анализ, обобщение и систематизация изученного материала.

Актуальность:

Простые числа с давних времен привлекают внимание математиков. Простые числа следует одно за другим по закону, который еще не найден. Но простые числа в математике играют важную роль. Из них с помощью умножения получаются все остальные числа. Хорошо было бы, если все простые числа можно было сосчитать! Но эта проблема до сих пор остается нерешенной. Как сказал Евклид: самого большого простого числа не существует.

Гипотеза:

Если эти числа называются «простыми», то все эти числа давно изучены и про них уже все известно.

Основная часть

1.Простые числа и их свойства

Сложно сказать, когда люди впервые задумались о простых числах, некоторые ученые предполагают, что это произошло более двадцати тысяч лет назад. На папирусах древних египтян  были найдены ряды простых чисел. Древние греки тоже внесли свой большой вклад в историю возникновения простых чисел. Евклид нашел и доказал различные свойства простых чисел. Когда римляне завоевали Грецию, они сохранили все их математические исследования и перевели их на латинский язык. Арабские математики, изучив исследования греков, также внесли свой вклад в историю возникновения простых чисел.

Ко времени появления работы Евклида «Начала» в 300 в. до н.э. , уже было доказано несколько важных фактов касательно простых чисел. В своей книге Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного.

Евклид определял простые числа так: “Простое число есть измеряемое только единицей”. Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя.  Например, 5,7,13, 47.

Рассмотрев числовой ряд простых чисел, мы обратили внимание на то, что:

1. Единица, имеющая только один делитель, к простым числам не относится. Не относится она и к составным числам. Единица занимает особое положение в числовом ряду. Пифагорейцы учили, что единица — матерь всех чисел, дух, из которого происходит весь видимый мир, она есть разум, добро, гармония. Единица и в самом деле — число уникальное по свойствам: она делится только сама на себя, но любое другое число на нее делится без остатка, любая ее степень равна тому, же самому числу — единице! После деления на нее ни одно число не изменяется, а если и поделить любое число на самое себя, получится опять же единица! Не удивительно ли это? Поразмыслив над этим, Эйлер заявил: «Нужно исключить единицу из последовательности простых чисел, она не является ни простым, ни составным».

2. Единственное чётное простое число 2. Все остальные простые числа нечётные. Любое другое четное число сюда попасть попросту не может, так как уже по определению, кроме себя и единицы, делится еще и на два.

3.Как и множество натуральных чисел, множество простых чисел бесконечно. Простые числа никогда не прерываются и никогда не заканчиваются.

3.Простые числа – близнецы.

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

Сколько всего существует близнецов — современной науке неизвестно. По мере удаления от нуля близнецы встречаются всё реже и реже.

2. Способы нахождения простых чисел.

Поиск простых чисел — одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Над поиском максимально больших простых чисел в своё время бились Катальди, Рене Декарт, Пьер Ферма, Марен Мерсенн, Эйлер и многие другие математики.

Распределение простых чисел в натуральном ряду

  1. Открытие П.Л. Чебышева

Как же распределены простые числа в натуральном ряду, в котором не будет ни одного простого числа? Есть ли какой-нибудь закон в их распределении или нет?

Большой шаг в разрешении этого вопроса сделал великий русский ученый Панфутий Львович Чебышев. В 1850 г. он доказал, что между любым натуральным числом (не равным 1) и числом, в два раза больше его (т. е. между n и 2n), находится хотя бы одно простое число. 

  1. Скатерть (спираль) С. Улама.

Как гласит легенда, однажды математику довелось присутствовать на очень длинном и скучном докладе. Чтобы развлечься, он начертил на листке бумаги вертикальные и горизонтальные линии, чтобы заняться составлением шахматных этюдов, но потом передумал и начал нумеровать пересечения, поставив в центре 1, и, двигаясь по спирали против часовой стрелки, записывал все натуральные числа до 100. Без всякой мысли Улам обводил все простые числа кружками. Каково было его удивление, когда он увидел, что простые числа стали выстраиваться вдоль диагональных прямых линий!

Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел. Разработав программу, Улам получил рисунок для чисел от 1 до 65 000, из которого видно, что даже у края картины простые числа продолжают послушно укладываться на прямые.

Эйлер, Ферма, Лежандр и многие другие известные математики пытались и пытаются по сей день разгадать загадку простых чисел.

  1. Применение простых чисел

«Если так трудно найти следующее простое число, то где и для чего эти числа можно использовать на практике?» Наиболее распространенным примером использования простых чисел является применение их в криптографии (шифровании данных). Простые числа — столп всех систем криптографии.  Самые безопасные и трудно дешифруемые методы криптографии основаны на применении простых чисел, имеющих в составе более трех сотен цифр. Давайте попробуем проиллюстрировать проблему, с которой сталкивается дешифровщик для расшифровки пароля. Допустим, паролем является один из делителей составного числа, а дешифровщиком выступает человек. Возьмем число из первого десятка, например, 8. Каждый человек способен в уме разложить число 8 на простые множители – 8=2*2*2. Усложним задачу: возьмем число из первой сотни, например, 111. В этом случае 111 быстро разложат в уме на множители люди, знающие признаки делимости числа на 3, и действительно — 111=3*37. Усложняя задачу, возьмем число из первой тысячи, например 1207. Человеку (без использования машинной обработки) потребуется, как минимум, бумага и ручка, для того чтобы перепробовать деление числа 1207 на «все» предшествующие этому числу простые числа. И только перебрав последовательно деление 1207 на все простые числа от 2 до 17 человек, наконец то, получит второй целый делитель данного числа – 71. Однако и 71 необходимо так же проверить на простоту.

Становится понятно, что с увеличением разрядности чисел, например, пятизначного числа — 10001, разложение без машинной обработки займет большое количество времени. Современный этап развития компьютерной техники (доступный рядовому пользователю) позволяет за считанные секунды раскладывать на множители числа, состоящие из шестидесяти цифр.

На сегодняшний день разложить числа, состоящие из тысячи и более цифр, способны только компьютеры.  Именно с их помощью ученные находят все новые и новые, наибольшие из известных, простые числа.

4. Практическая работа:

1. Рассмотрим числа близнецы. В пределах первой сотни близнецы – это следующие пары чисел:

Числа — близнецы

Сумма чисел – близнецов кратна 3

3 и 5

5 и 7

5 + 7 = 12 кратно 3

11 и 13

11 + 13 = 24 кратно 3

17 и 19

17 + 19 = 36 кратно 3

29 и 31

29 + 31 = 60 кратно 3

41 и 43

41 + 43 = 84 кратно 3

59 и 61

59 + 61 =120 кратно 3

n

n : 3

остаток

n + 2

(n + 2) : 3

остаток

5

1

2

7

2

1

11

3

2

13

4

1

17

5

2

19

6

1

29

9

2

31

10

1

41

13

2

43

14

1

101

33

2

103

34

1

Более того (за исключением первой пары), при делении на тройку левого собрата в остатке всегда остается двойка, а правого – единица.

2. При делении на 30  все квадруплеты, кроме первого и второго, дают одну и ту же четвёрку остатков:

(11, 13, 17, 19).

Проверим:

(101, 103, 107, 109)

101: 30 = 3 (остаток 11), 103 : 30 = 3 (остаток 13), 107 : 30 = 3 (остаток 17), 109 : 30 = 3 (остаток 19)

(191, 193, 197, 199)

191 : 30 =6 (остаток 11), 193 : 30 = 6 (остаток 13), 197 : 30=3 (остаток 17), 199 : 30 = 6 (остаток 19)

3.В практической части своей работы мы решили проверить теорию Чебышева на несложных примерах. Примем для n несколько произвольных значений и найдем соответственно значение 2n.

n = 11, 2n = 22; простые числа: 13,17,19

n = 25, 2n = 50; простые числа: 29,31,37

n = 54, 2n = 108; простые числа: 59,61,67

n = 99, 2n = 198; простые числа: 101,103,107

Мы определили, что для рассмотренных примеров теорема Чебышева верна. Чебышев доказал ее для любого случая, для любого n. За эту теорему его назвали победителем простых чисел.

4.При подготовке проекта нам мне встречались интересные факты про простые числа. Вот один из них.

В 18 веке были открыты простые числа:

 31, 331, 3331, 33331, 333331, 3333331, 33333331.

Удивительно, но следующее число 333333331 не является простым, оно делится на 17.

Заключение

Проведя свои исследования и анализируя научно-популярную литературу, я сделал следующие выводы:

  1. Для простых чисел не существует 100% доказанной формулы или закономерности, описывающих распределение простых чисел в бесконечном натуральном ряду.
  2. Не существует самого большого простого числа, последовательность простых чисел бесконечна.
  3. Многие ученые на протяжении многих веков вносили свой вклад в изучение темы «Простые числа».
  4. Простые числа не совсем соответствуют значению и определению слова «простой». По своей сути они очень сложны, многогранны и хранят много тайн, неизвестного. Наша гипотеза не подтвердилась.
  5. В настоящее время исследование простых чисел  продолжается.

«Всякий, кто изучает простые числа, бывает очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители — такое естественное действие. Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?»

Ч. Узерелл

Список литературы:

1. Гальперин Г. «Просто о простых числах» // Квант. — № 4. — С. 9-14,38.

2.  Интернет ресурсы:

http://www.numbernautics.ru/chislonautics/804-2012-05-25-14-38-53

http://fb.ru/article/60293/prostyie-chisla-obyidennost-nerazgadannoy-zagadki

http://ru.wikipedia.org/wiki/Простое_число

https://vallentinn.livejournal.com/150597.html

http://www.etudes.ru/en/

  • Мне нравится

Каргопольская игрушка

Чем пахнут ремёсла? Джанни Родари

Нечаянная победа. Айзек Азимов

Рисуем гуашью: «Кружка горячего какао у зимнего окна»

5 зимних аудиосказок

image—> —> image

Итак, продолжаю выкладывать наиболее востребованные исходники Паскаль ABC по теме циклы паскаль (FOR). Задача Pascal такая: Дано натуральное число. Найти все его делители и их сумму. Число вводится с клавиатуры, делители выводятся через пробелы, сумма в следующей строке. Допустим диалог с пользователем. Исходный код программы:

Var n, i, sum: integer;  //Описание переменных Begin                    //Начло программы writeln ('Введите число'); //Диалог с пользователем readln(n);                  //Считывание числа sum := n;                   //Присваивание сумме значение самого числа (само число - уже делитель самого себя) writeln('Делители числа:');   //Диалог с пользователем for i := 1 to n div 2 do      //Цикл For от до половины n   if (n mod i) = 0 then begin  //Если число делится на i, то выводим     write(i,'  ');     sum := sum + i;            //К значению суммы прибавляем делитель   end;                         //Конец условного оператора if writeln(n); //Вывод самого числа, т.к. оно тоже делитель writeln('Сумма делителей: ',sum);  //Вывод суммы делителей End.                               //Конец программы

Скачать программу паскаль:pas19for.pas

Похожие публикации: Программа на паскаль, которая находит числа у которых сумма цифр трехзначного числа кратна 7, а само число также делится на 7Исходник программы, которая выводит двухзначные числа с цифрой n или кратные nИсходник программы, которая находит факториал числаИсходник программы, которая находит минимальное число, большее 300 и делящееся нацело на 19Исходник программы Паскаль, которая находит корни квадратного уравнения по заданным коэффициентам

Оцените статью
Рейтинг автора
5
Материал подготовил
Илья Коршунов
Наш эксперт
Написано статей
134
А как считаете Вы?
Напишите в комментариях, что вы думаете – согласны
ли со статьей или есть что добавить?
Добавить комментарий