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

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

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



----------------
С уважением
...
Рейтинг: 0 / 0
29.06.2007, 11:17
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #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, 11:20
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #34628501
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
qwedfg wrote:

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

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

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

аффтопитезь: 4 8 15 16 23 42
...
Рейтинг: 0 / 0
01.07.2007, 10:36
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #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
01.07.2007, 16:40
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #34633422
IcyCool
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
IcyCool
Участник
Если
for(int i=2;i<=ub;i++)
заменить на
for(int i=2;i<=ub;i+=2)

То будет уже в два раза шустрее
...
Рейтинг: 0 / 0
02.07.2007, 20:00
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #34633425
ZeusTheTrueGod
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZeusTheTrueGod
Участник
Для каких целей нужны простые числа автору?
...
Рейтинг: 0 / 0
02.07.2007, 20:04
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #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, 20:55
| Ответить | Цитировать | Написать  
Алгоритм нахождения простых чисел
    #34633501
ErV
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ErV
Участник
qwedfg wrote:

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

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

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

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

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

Например:

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

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

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

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

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

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


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