![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
Простые числа.
Сидел на паре, и вдруг в голову стукнул алгоритм быстрого вычисления количества простых чисел на промежутке. Пришел домой и забацал карту, вроде все пашет:). Вот только трабла в том, что в WE стоит ограничение на величину массива около 8200 , поэтому максимальный промежуток 1-82. Однако метод подсчета реально быстрее чем перебор чисел. Скажите как увеличить массив. |
![]() |
#1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
NETRAT
![]() ![]() offline
Опыт:
83,712Активность: |
Сказал. Ты бы лучше алгоритм описал
NETRAT добавил: А вообще, что-то такое уже было... Оно хоть все числа вычисляет? |
![]() |
#2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
Навряд ли смогу обьяснить, препод по матемше и то меня не понял (в смысле, что объяснить трудно). А ты сам ломани карту и посмотри, там идет от обратного, т.е. вычисляется кол-во непростых чисел (не перебором, а гораздо быстрее) и отнимается от величины промежутка и еще -1 (т.к. 1 не простое число).
А сами простые числа он не вычесляет, хотя могу заделать. |
![]() |
#3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
MapMan
Corey 8 Taylor
![]() offline
Опыт:
21,554Активность: |
Iron а зачем эти ПРОСТЫЕ ЧИСЛА???
|
![]() |
#4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
Да так, просто из интереса. |
![]() |
#5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
NETRAT
![]() ![]() offline
Опыт:
83,712Активность: |
Суть понятна, но он слегка неоптимален - перебирать нужно до корня квадратного из числа и второй индекс начинать с первого for int t=0 bla fot in k=t bla |
![]() |
#6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
NETRAT У МЕНЯ НИЧЕГО НЕ ПЕРЕБЕРАЕТСЯ. Там состовляется что-то типа квадрата пифагора только в виде массива и все непопавшие в него числа не превышающие грани являются простыми.
|
![]() |
#7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
NETRAT
![]() ![]() offline
Опыт:
83,712Активность: |
Про штаны слыхал, а про квадрат нет =( ну, может проглядел я слегка индексы, без разницы - принцип понял - выкидываем все числа, которые составляют произведения двух других чисел и смотрим что остается |
![]() |
#8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
Элементарно, Ватсон. |
![]() |
#9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Markiz
![]() offline
Опыт:
11,432Активность: |
doodad data is missing or invalid.
офигеть. какая крутая карта. Markiz добавил: и самое главное, он просит заценить алгоритм перебора :up: |
![]() |
#10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
TiM
Старичок
![]() offline
Опыт:
8,594Активность: |
В чем смысл то? Объясни пожалуйста, а то качать и разбираться не хочется... Простые числа-это числа, которые можно представить как произведение двух других чисел? *целых |
![]() |
#11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
NETRAT
![]() ![]() offline
Опыт:
83,712Активность: |
Markiz зырь в корень - J файл =)
TiM которые как раз нельзя представить суть я уже описал |
![]() |
#12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Iron
Листовой
![]() ![]() offline
Опыт:
24,427Активность: |
TiM Простые числа - числа которые делятся нацело только на себя и на еденицу (не включая 1). Но вся фишка в том, что люди еще не смогли пока найти закономерности в их расположении в числовом ряду (а может ее и нет вовсе). Например: 2 3 5 7 11 13 17 19 23...
Так вот моя карта позволяет достаточно быстро найти количество простых чисел на отрезке от 1 до произвольного числа (пока не больше 82) причем не стандартным методом перебора (ну это когда все числа по очереди пытаются разделить на числа от 2 до своего квадратного корня, и те из них которые не разделились, считают простыми), а более скоростным методом. Не обижайтесь на то, что карта не совсем про вар, просто захотелось поламать мозг. |
![]() |
#13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
![]()
Inoriol
Я пришёл....
![]() ![]() offline
Опыт:
11,629Активность: |
прикольно сделано.молодец.варик для школьников.в 5 классе показывать |
![]() |
#14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|