Iron
Листовой
  offline
Опыт:
24,427Активность: |
Простые числа.
Сидел на паре, и вдруг в голову стукнул алгоритм быстрого вычисления количества простых чисел на промежутке. Пришел домой и забацал карту, вроде все пашет:). Вот только трабла в том, что в WE стоит ограничение на величину массива около 8200 , поэтому максимальный промежуток 1-82. Однако метод подсчета реально быстрее чем перебор чисел. Скажите как увеличить массив. |
05.01.2006, 17:01
|
|
NETRAT
 offline
Опыт:
83,712Активность: |
Сказал. Ты бы лучше алгоритм описал
NETRAT добавил: А вообще, что-то такое уже было... Оно хоть все числа вычисляет? |
|
05.01.2006, 17:10
|
|
Iron
Листовой
offline
Опыт:
24,427Активность: |
Навряд ли смогу обьяснить, препод по матемше и то меня не понял (в смысле, что объяснить трудно). А ты сам ломани карту и посмотри, там идет от обратного, т.е. вычисляется кол-во непростых чисел (не перебором, а гораздо быстрее) и отнимается от величины промежутка и еще -1 (т.к. 1 не простое число).
А сами простые числа он не вычесляет, хотя могу заделать. |
|
05.01.2006, 17:14
|
|
MapMan
Corey 8 Taylor
offline
Опыт:
21,554Активность: |
Iron а зачем эти ПРОСТЫЕ ЧИСЛА???
|
|
05.01.2006, 17:45
|
|
Iron
Листовой
offline
Опыт:
24,427Активность: |
Да так, просто из интереса. |
|
05.01.2006, 17:51
|
|
NETRAT
offline
Опыт:
83,712Активность: |
Суть понятна, но он слегка неоптимален - перебирать нужно до корня квадратного из числа и второй индекс начинать с первого for int t=0 bla fot in k=t bla |
|
05.01.2006, 17:56
|
|
Iron
Листовой
offline
Опыт:
24,427Активность: |
NETRAT У МЕНЯ НИЧЕГО НЕ ПЕРЕБЕРАЕТСЯ. Там состовляется что-то типа квадрата пифагора только в виде массива и все непопавшие в него числа не превышающие грани являются простыми.
|
|
05.01.2006, 17:59
|
|
NETRAT
offline
Опыт:
83,712Активность: |
Про штаны слыхал, а про квадрат нет =( ну, может проглядел я слегка индексы, без разницы - принцип понял - выкидываем все числа, которые составляют произведения двух других чисел и смотрим что остается |
|
05.01.2006, 18:10
|
|
Iron
Листовой
offline
Опыт:
24,427Активность: |
Элементарно, Ватсон. |
|
05.01.2006, 18:55
|
|
Markiz
offline
Опыт:
11,432Активность: |
doodad data is missing or invalid.
офигеть. какая крутая карта. Markiz добавил: и самое главное, он просит заценить алгоритм перебора :up: |
|
05.01.2006, 19:55
|
|
TiM
Старичок
offline
Опыт:
8,594Активность: |
В чем смысл то? Объясни пожалуйста, а то качать и разбираться не хочется... Простые числа-это числа, которые можно представить как произведение двух других чисел? *целых |
|
05.01.2006, 20:00
|
|
NETRAT
offline
Опыт:
83,712Активность: |
Markiz зырь в корень - J файл =)
TiM которые как раз нельзя представить суть я уже описал |
|
05.01.2006, 20:49
|
|
Iron
Листовой
offline
Опыт:
24,427Активность: |
TiM Простые числа - числа которые делятся нацело только на себя и на еденицу (не включая 1). Но вся фишка в том, что люди еще не смогли пока найти закономерности в их расположении в числовом ряду (а может ее и нет вовсе). Например: 2 3 5 7 11 13 17 19 23...
Так вот моя карта позволяет достаточно быстро найти количество простых чисел на отрезке от 1 до произвольного числа (пока не больше 82) причем не стандартным методом перебора (ну это когда все числа по очереди пытаются разделить на числа от 2 до своего квадратного корня, и те из них которые не разделились, считают простыми), а более скоростным методом. Не обижайтесь на то, что карта не совсем про вар, просто захотелось поламать мозг. |
|
06.01.2006, 10:29
|
|
Inoriol
Я пришёл....
 offline
Опыт:
11,629Активность: |
прикольно сделано.молодец.варик для школьников.в 5 классе показывать |
|
18.02.2006, 22:28
|
