Простые числа интересные факты. Интересные факты о числах:

Простые числа интересные факты. Интересные факты о числах:

1. Знаете, как называется самое большое число? Ему дали название Центильон. Записывается оно как «1» и 600 нулей. Впервые число было записано в начале 1852 года.
2. В арабских странах цифры записываются не так, как в европейских, – справа налево, начиная с меньшего разряда. Именно поэтому, увидев арабские обозначения в текстах, мы по привычке будем их читать слева направо, а значит – прочитанное будет неправильным.
3. Не обошли интересные факты о числах иинновационные технологии. Например, корпорация Google – одна из самых крупных и успешных поисковых систем на просторах Интернета. Ее создатели Sergey Brin и Larry Page особое внимание уделяли выбору названия для своего творения. Придумав название «Google»,разработчики хотели рассказать о количестве информации, которую способна обработать система. «Гугол» – именно такое название носит число, включающее в себя единицу и сотню нулей. Удивительно, но название поисковой системы записано не совсем верно, вместо «googol» было решено отдать предпочтение слову «Google»
4. «13» – число, которое относится к одному из самых несчастливых в Греции, однако, это распространяется только на дату, выпадающую на вторник. Итальянцы боятся 17-го числа, приходящегося на пятницу. А ученные из Нидерландов провели исследование, в результате которого было установлено, что на число 13 приходится наименьшее количество дорожно-транспортных происшествий, несчастных случаев и прочих напастей, что связанно с особой осторожностью и сосредоточенностью людей.
5. Слово «Цифра» переводится с арабского языка как «0». Однако, с течением времени это название начали применять для обозначения любого числа не только в арабских странах, но и по всему миру.
6. Считается, что цифра «7» относится к самым счастливым. Человек, которого сопровождает это число, является более удачливым.
7. Нашлись и необычные факты в мире насекомых. Так, нелюбимая многими сороконожка имеет вовсе не 40 пар ножек. Их количество может варьировать от тридцати до четырехсот.
8. При старте вес космического челнока достигает 2000 тонн.
9. Мы нередко наслаждаемся зрелищем, когда на небе собирается множество облаков. Стоит знать, вес одного облака в среднем составляет пятьсот тонн.
10. Одно из самых толстых печатных изданий было выпущено в Нью-Йорке в 1965 году – газета The New York Times состояла из 946 страниц, а ее вес был близок к 3,5 кг.
11. Если получить миллион долларов купюрами по $100, вес денег будет равняться девяти килограммам;
12. Земля богата различными ископаемыми и иными ресурсами, однако, есть материалы, которые на вес золота, – общий вес Астата, находящегося в земной коре по всему миру, составляет не более 0,16 грамм. Все потому, что Астат сильно радиоактивен. С греческого языка Астат значит "неустойчивый".
13. Спутниковое телевидение сегодня предпочитают многие люди. Вы когда-нибудь задавались вопросом, на каком расстоянии расположен спутник, с помощью которого осуществляется трансляция телевизионных каналов? Он расположен на расстоянии 35 000 км.
14. Голубой кит – крупное млекопитающее, а длина его языка составляет целых три метра!
15. В книге Рекордов Гиннеса зафиксирован самый крупный домашний кот, его длина составила 1,23м. Порода - Мейн-кун.

Как найти простые числа. Алгоритмы нахождения простых чисел

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

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

Задача 1. Определение простого числа.

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

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале . Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

var n,i: longint; flag: boolean; begin writeln('vvod n'); read(n); if n = 2 then flag := true      else if not odd (n) then flag := false          else  begin                flag := true;                for i := 2 to n-1 do                if n mod i = 0 then flag := false                end; if flag then writeln('Yes') else writeln('No'); readln; end.

Задача 2. Нахождение простых чисел в заданном интервале.

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

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, - простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

1. рассматривать только нечетные числа;
2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

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

var m,n,i,k: longint; flag: boolean; begin writeln('vvod m>3'); readln(m); write('      2      3'); n:=3; k := 2;  n := n+2; while n

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

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

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

var m,n,n1,n2,i,k: longint; flag: boolean; begin m :=1000; n1 := 2; n2 := 3; n := n2+2; k:=0; while n

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

var m,n,i,k: longint; flag: boolean; f:text; begin assign(f,'output.txt'); rewrite(f); writeln('vvod m > 3'); readln(m); write(f,'  2  3'); n:=3; k := 2;  n := n+2; while n

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

1. Вводим правую границу диапазона – m;
2. Записываем двойку и тройку в файл;
3. Пока очередное нечетное число i
4. проверять очередное нечетное число на наличие делителей из данного файла;
5. если есть делители, рассматривать очередное нечетное число, если нет - производить дозапись в “хвост” файла.

По окончании просмотра диапазона ( i > m ), вывести в файл количество простых чисел.

{Простые до m}   label n1;   var   m,i,j,k,q : longint;   f : text;   begin      assign(f,'output.txt');      rewrite(f);      Writeln('vvod m');  {m – правая граница диапазона чисел}      readln(m);      k := 0;             {k – счетчик количества простых чисел}      if m >= 2 then begin                   write(f,' ':6,'2',' ':6);                   k:=k+1                 end;      if m >= 3 then begin                  write(f,'3');                  k:=k+1                end;      close(f);      i:=5;                {В i находится текущее нечетное число}      while i i) then break;            if (i mod q=0) then goto n1           end;        close(f);             {дозапись в ‘хвост’ файла простых чисел}        append(f);            k:=k+1;            Write (f,i:7);            if k mod 10 = 0 then writeln(f);            close(f);        {следующее нечетное число I

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

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале . Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод. 

Пусть написаны числа от 2 до n:

2 3 4 5 6 7 8 9 10 11 12 . . .

Как определить простое число. Как узнать простое число по его номеру

Время чтения: 7 минут

Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.

Чтобы проверить является ли какое-то число простым, напрашивается наивный метод решения - проверить делимость его на все натуральные числа от 1 до n (хотя достаточно лишь до квадратного корня из него). Если в какой-то момент остаток от деления даст 0 (то есть число поделилось без остатка), значит оно составное, а в противном случае является простым.

Такой алгоритм прост, но требует довольно много проверок на делимость, из-за чего может быть применён для проверки небольшого числа. А что будет, если применить его для поиска простого числа по заданному номеру n?

Решение кажется очевидным: начнём перебирать подряд числа и проверять их на простоту. Как только обнаружим n простых чисел, остановимся и вернём в результате последнее найденное число. Однако, даже для не очень большого числа n данный метод будет работать чрезвычайно долго, поскольку чем больше будет число, тем дольше будут перебираться его делители.

Вот тут нам на помощь и приходит быстрый алгоритм — решето Эратосфена . Данный алгоритм позволяет найти все простые числа в интервале от 2 до N за довольно короткое время, но нам то нужно найти n-ое простое число, а про индексы в данном алгоритме ничего не сказано. Если бы можно было узнать, в каком интервале находится n-ое простое число, то задача была бы мгновенно решена применением решета. Однако как же решить данную задачу, не зная примерное значение числа?

Как работает решето Эратосфена

Мы предлагаем следующее решение: получим число n и создадим два массива размерности n: primes - массив для хранения будущих простых чисел и numbers - массив для хранения обычных чисел для применения просеивания решетом. Заполним массив numbers числами от 0 до n - 1, а в нулевой элемент массива primes положим 2, поскольку 2 — первое простое число.

Код программы для поиска простого числа по его номеру

#include int main () { int n; std::cout > n; // считываем номер простого числа, которое нужно найти int size = n; // число элементов для массива чисел для просеивания int *primes = new int; // массив простых чисел int *numbers = new int; // массив для чисел for (int i = 0; i = size) { // если выйдем за границы, расширяем массив int *tmp = new int; for (int k = 0; k

Теперь нам нужно искать числа до тех пор, пока не найдём все n, поэтому обнуляем переменную i, обозначающую текущий индекс простого числа и запускаем цикл пока с условием i

Запоминаем в переменной p текущее простое число (на первой итерации это будет 2), увеличивая текущий индекс простого числа на 1 и просеивая массив чисел от 2p до размера массива чисел (тем элементам массива, где стоят кратные p числа (кроме самого p), проставляем нули, после чего ищем первое ненулевое число — оно и будет следующим простым числом.

В дальнейшем может возникнуть проблема, что n-ое простое число ещё не найдено, а массив чисел уже закончился. Простым решением данной проблемы будет увеличение его размера в два раза и до заполнение числами. Но если так сделать, то в нём останутся числа, кратные тем, что ещё уже были просеяны, и требуется их обработать. Простым решением данной проблемы является запуск алгоритма сначала, а именно обнуление индекса текущего простого числа, благодаря чему все операции просеивания будут проведены повторно, но уже для нового более длинного массива.

Если же изменение массива не требовалось, в массив primes просто записывается найденное простое число (первое ненулевое число в массиве numbers).

Когда же цикл завершён, достаточно просто вывести n - 1 элемент в массиве primes или весь массив, если нужны все простые числа до указанного номера.