Меню сайта
Наш опрос
Оцените мой сайт
Всего ответов: 5
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » 2014 » Июль » 22 » Простые числа. Решето Эратосфена
15:28
Простые числа. Решето Эратосфена
Вас интересует сеть ресторанов в Санкт-Петербурге? Тогда зайдите на специальный сайт parkking.ru в интернете.

Вернемся к простым числам. Есть алгоритм, по которому легко вычислить все простые числа до какого-то заданного числа N - это решето Эрастофена. Суть его в следующем: запишем все числа от 1 до N в ряд. Так как число 1 не простое, то его не рассматриваем, т.е. вычеркиваем (число, которое вычеркиваем - подчеркнуто, а простое - выделено полужирным).1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N1. Берем следующее невычеркнутое число 2.2. Проверяем все числа от 3 до N на делимость на 2. Если число делится на 2 без остатка, то вычеркиваем его.1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N4. Переходим к следующему невычеркнутому числу - это 3, и повторяем п.2, но уже числа проверяем с 4 до N и проверяем делимость на 3.1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,N5. Переходим к следующему невычеркнутому числу - это 5, и повторяем п.2, но уже числа проверяем с 6 до N и проверяем делимость на 5.1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...,Nи т.д.Видно, что алгоритм можно оформить в виде циклов. Для проверки делимости можно использовать операцию mod - взятие остатка. Вопрос: как оформить процесс вычеркивания в Паскале?Есть несколько способов: с помощью структурированных типов множество, массив или строки.C помощью множестваМножество целых чисел не превышает значения 255. Если число не простое - исключаем его из множества. Перед работой присваиваем множеству диапазон чисел от 2 до N. :Var M:set of byte;    i,k,N:byte;begin{ввод и инициализация}    ',i);end.C помощью массиваЛучше использовать массив с элементами логического типа. Будем считать, что на i-ом месте массива P стоит true (или 1) если число простое, иначе false (или 0). Перед работой массив нужно  "проинициализировать" значениями true (или 1), т.е. считаем, что все числа простые (как при доказательстве от противного):Var P:array [2..65535] of boolean;    i,k,N:word;begin{ввод и инициализация}    readln(N);    ',i);end.C помощью строкБудем считать, что на i-ом месте строки S стоит '*' если число простое, иначе ' ' (пробел). Перед работой со строкой нужно ее "инициализировать" символами '*', т.е. считаем, что все числа простые (как при доказательстве от противного). Кроме этого нужно знать, что строка содержит не более 255 символов (как сделать еще больше? Создать массив символов - это другой способ):Var S:string[255];    i,k,N:byte;begin{ввод и инициализация}    readln(N);    fillchar(S,N,'*');    S[1]:=' )and(i mod ;    inc(k);    while ) do inc(k);    until k>N;{вывод ряда простых чисел}    for then write(' ',i);end.Я специально привела три способа, чтобы показать какие есть возможности у Паскаля для реализации этого алгоритма. каждый алгоритм имеет свои ограничения на конечное число: 255 и 65535. Можно попробовать написать программу с использованием указателей на ячейку памяти. Тогда ограничение для чисел здесь увеличивается до типа longint или comp, а если написать операцию проверки делимости для вещественных чисел, то и для extended (самого большого числа). Но для вещественных чисел нужно менять цикл for на While, что может привести к увеличению времени работы алгоритма.Пробуйте.PS: Кроме этого разбора я показала один из приемов в обучении: чтобы запомнить алгоритм - нужно его попробовать написать другим способом и если через некоторое время переменные, операторы, типы будут схожи, то вы выработали свой стиль программирования и запомнили алгоритм. Удачи.


ремонт электроплит аристон

 

 

Просмотров: 431 | Добавил: admin | Рейтинг: 0.0/0
Всего комментариев: 0
avatar
Форма входа
Календарь
«  Июль 2014  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031
Архив записей