Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм нахождения простых чисел / 25 сообщений из 84, страница 1 из 4
  1  все
29.06.2007, 10:37
    #34627970
qwedfg
qwedfg
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Существует-ли такой ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 10:45
    #34628025
1211212
1211212
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Все в числе, на интервале значений чисел?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 11:00
    #34628085
Nikolay B.
Nikolay B.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
qwedfgСуществует-ли такой ?
Да.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 11:17
    #34628141
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
1) Для ограниченного диапазона применяют Решето Эратосфена. (Требует дополнительной памяти в виде битовой карты, соизмеримой с диапазоном).

2) Для монотонной последовательности простых чисел (ППЧ) я писал довольно шустрый алгоритм на С++. Могу поискать, если интересно. Правда он работает в диапазоне 32-разрядных целых. А при переходе в более высокую разрядную сетку нужно скачкообразно менять технологию и поэтому на дальнейшие оптимизации я забил. Вообще, спустя много лет, я понял, что затея с написанием универсального алгоритма генерации последовательности простых чисел - из области поиска "философского камня" . Можно достичь успеха в любых смежных с ней областях (теория чисел, криптография) но сам метод будет всегда в состоянии бета-версии. Кстати, проводить соревнования по скорости числогенерации - бесполезное занятие, поскольку финишная черта - находится в бесконечности, а именно там и проявляют себя основные свойства ППЧ. И алгоритм, который на старте дал приличную скорость, в более серъезном диапазоне может полностью провалится (на радость математикам и в назиданиие любителям кодировать в АСМ-е ).

3) Если нужно просто сгенерировать одно простое число (ОООЧЕНЬ БОЛЬШОЕ), используются генерация случайного числа с проверкой его на простоту специальными быстрыми тестами. Они гарантируют "простоту" с очень высокой вероятностью 99.9999...
Этот метод используют в криптографии.



----------------
С уважением
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 11:20
    #34628153
4321
4321
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
qwedfgСуществует-ли такой ?один из первых известных - "решето эратосфена"
http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 12:40
    #34628501
ErV
ErV
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
qwedfg wrote:

> Существует-ли такой ?
Да. Поройтесь на википедии и поищите гуглом, я где-то (вроде бы в википедии)
видел несколько элегантных алгоритмов, более интересных, чем "решето". К
сожалению, найти пока не могу, где это было.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.06.2007, 19:56
    #34629740
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Для маленьких чисел можно применить табличный метод, используя уже найденные числа :)

А если придумать хороший алгоритм, можно неплохо подзаработать ;)

так что, автор- дерзай!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.07.2007, 10:36
    #34630529
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
могу дать почту одного человека, он находил простые числа вроде б от 1 до десятков миллионов и довольно быстро. если не ошибаюсь, за час примерно.

аффтопитезь: 4 8 15 16 23 42
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.07.2007, 16:40
    #34630695
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Вот простая генерилка. Не использует дополнительную память. На моём Celeron 1.7 Ghz выдаёт за 5 секунд все числа в диапазоне от 3 до 1000000.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
package ua.dn.mayton.math;

public class PrimeGeneratorSimple implements INumGenerator {

    protected int c= 1 ;
    
    public int getNext()
    {           
        while(true){
            c+= 2 ;
            int ub=(int)Math.sqrt((double)c);
            boolean isprime=true;
            for(int i= 2 ;i<=ub;i++)
            {
                if ((c%i)== 0 ) {isprime=false;break;}
            }
            if (isprime) break;
        }
        return c;
    }

    public boolean hasNext() {
        return true;
    }

    public void reset() {
        c= 1 ;
    }
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.07.2007, 20:00
    #34633422
IcyCool
IcyCool
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Если
for(int i=2;i<=ub;i++)
заменить на
for(int i=2;i<=ub;i+=2)

То будет уже в два раза шустрее
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.07.2007, 20:04
    #34633425
ZeusTheTrueGod
ZeusTheTrueGod
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Для каких целей нужны простые числа автору?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.07.2007, 20:55
    #34633469
miksoft
miksoft
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
IcyCoolЕсли
for(int i=2;i<=ub;i++)
заменить на
for(int i=2;i<=ub;i+=2)

То будет уже в два раза шустрееТ.е. делимость на 3 предлагате не проверять?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.07.2007, 21:31
    #34633501
ErV
ErV
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
qwedfg wrote:

> Существует-ли такой ?
Был хороший простой двоичный алгоритм нахождения простых чисел, очень
быстрый.
Проблема: забыл, где видел и как называется :-(
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
31.07.2007, 14:24
    #34695601
Alex_soldier
Alex_soldier
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Есть такая теоремка:
Пусть Х - тестируемое число.
Если A^X mod X = А для всех A = 2 ... X-1,
то X - простое.

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

Для чисел специального вида существуют хитрые и точные методы.
Тут уже нужно подробнее узнать о целях автора!

---
Идеи движут Мир!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.08.2007, 09:21
    #34705932
I
I
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Генерируется случайное нечётное большое число и проверятся, например, с помощью вероятностного теста Миллера - Рабина
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.08.2007, 14:30
    #34707872
Хитроглазый
Хитроглазый
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
кроме перебора - не существует
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.08.2007, 15:01
    #34708013
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Хитроглазыйкроме перебора - не существует

Я - бы не стал торопится с таким заявлением. К примеру, если вам известена монотонная последовательность простых чисел (2,3,5,7,11,13) то найти следующее простое число довольно просто. Можно перемножить числа последовательности и добавить 1. Этот метод - не переборный.

Например:

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031

Это число простое по определению. Правда, этот метод не даёт возможности найти числа в окрестности выше 13.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 10:18
    #34709605
Alex_soldier
Alex_soldier
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Хитроглазыйкроме перебора - не существует
Перебор - самый "тупой" и громоздкий способ.
Уже для 100-значных чисел потребовалось бы много машино-лет на перебор всех делителей до 10^50.
А рекорд сейчас - 9,808,358 знаков!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:02
    #34710110
Хитроглазый
Хитроглазый
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
mayton2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031
Это число простое по определению
30031 = 59*509 и ага ;)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:36
    #34710298
4321
4321
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
mayton К примеру, если вам известена монотонная последовательность простых чисел (2,3,5,7,11,13) то найти следующее простое число довольно просто. Можно перемножить числа последовательности и добавить 1. Этот метод - не переборный.

Например:

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031

Это число простое по определению.в формулировке пропущена часть. "пердположим, известны _все_ простые числа..." далее - было бы по тексту. И вообще говоря - это всего лишь фрагмент доказательства бесконечного числа простых чисел. В силу отказа от предположения о конечности и известности алгоритм не верен.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:39
    #34710323
ErV
ErV
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Хитроглазый wrote:

> 30031 = 59*509 и ага ;)
очевидно, имелось в виду правило

Натуральное p > 1 является простым тогда и только тогда, когда (p - 1)! + 1
делится на p

Только это тест.

А как насчет
2^(2^n)+1 ?

и вот:
http://www.codenet.ru/progr/alg/Simple-Numbers.php
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:56
    #34710439
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
Хитроглазый30031 = 59*509 и ага ;)

Верно! Вы меня подловили.

Ваш ник вам - соответствует.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:57
    #34710449
ErV
ErV
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
mayton wrote:

> Верно! Вы меня подловили.
>
> Ваш ник вам - соответствует.
Нашел-таки я тот алгоритм, о котором раньше писал.
2^n-1
(http://ru.wikipedia.org/wiki/Число_Мерсенна)
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2007, 12:59
    #34710456
ErV
ErV
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
ErV wrote:

> (http://ru.wikipedia.org/wiki/Число_Мерсенна)
И довесок. http://ru.wikipedia.org/wiki/Тест_Люка_?_Лемера

Млин. это не тот алгоритм...
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
09.10.2008, 23:26
    #35586885
BeastIv
BeastIv
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм нахождения простых чисел
господа кодеры, а для Borland 3.1 можно вас попросить код написать?
а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм нахождения простых чисел / 25 сообщений из 84, страница 1 из 4
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 477ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1342169]:
 0ms
get settings:
 7ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 163ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 76ms
get tp. blocked users:
 1ms
others: 192ms
total:  477ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]