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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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

Например:

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

Это число простое по определению.в формулировке пропущена часть. "пердположим, известны _все_ простые числа..." далее - было бы по тексту. И вообще говоря - это всего лишь фрагмент доказательства бесконечного числа простых чисел. В силу отказа от предположения о конечности и известности алгоритм не верен.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #34710323
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
Алгоритм нахождения простых чисел
    #34710439
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хитроглазый30031 = 59*509 и ага ;)

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

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

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

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

Млин. это не тот алгоритм...
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
Алгоритм нахождения простых чисел
    #35586885
BeastIv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
господа кодеры, а для Borland 3.1 можно вас попросить код написать?
а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример...
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #35587231
Фотография Aklin J
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Nikolay B. qwedfgСуществует-ли такой ?
Да.

НЕТ

для малых чисел - решето Эратосфена
для больших вероятностные тесты

в общем случае берется произвольное число, затем в любую сторону шлепается до тех пор, пока не найдется простое. в реальности количество шагов (СРЕДНЕЕ) имеет зависимость, (только среднее!) вроде логарифма. (среднее, т.е. если надо найти К чисел друг за другом). в отдельном случае количество шагов не определено.

есть gnu mp библиотека (на сегодня самая быстрая для многих платформ), там есть ген больших чисел.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #35587234
Фотография Aklin J
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BeastIvгоспода кодеры, а для Borland 3.1 можно вас попросить код написать?
а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример...

борланд мертв

в вашем случае - найти одно число и проверить n+2 на простоту.
никак иначе
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #35589126
TeXpert
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если реализация конкретных алгоритмов интересуют, то можно посмотреть исходные тексты функций в пакетах Mathematica и Maple
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
Алгоритм нахождения простых чисел
    #36572545
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
как определить более-менее оптимально что число простое?
нутром чую что не надо пробегать от 2 до n-1 и делить, так как уже выше н/2 это заведомо будет чтото дробное с единицей в целой части. Еще какие приколы?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572580
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот алгоритм мой (простейший, зато верный)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
class CheckSimple
{
public:
	static bool IsSimple(__int64 val)
	{
		bool res = true;

		for (__int64 i =  2 ; i < val /  2  +  1 ; ++i)
		{
			double rem = val % i;

			if (val % i ==  0 )
				return false;
		}

		return res;
	}

};
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572582
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
даже так

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
class CheckSimple
{
public:
	static bool IsSimple(__int64 val)
	{
		bool res = true;

		for (__int64 i =  2 ; i < val /  2  +  1 ; ++i)
			if (val % i ==  0 )
				return false;

		return res;
	}

};
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572585
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Делители в диапазоне от 2 до корня квадратного от val.

И четные выше двух не учитывать.
И тройки выше трёх не учитывать.
И пятёрки... короче ты понял.

Направлений в оптимизации - масса.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572587
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну четные еще можно пожалуй более оптимально определить чем поделить, но тройки, пятерки и так далее непонятно как.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572589
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
+=3 && +=5
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572592
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
не понял
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572834
zloyGamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
простое число делится только на 1 и на само себя без остатка,
значит не делится на 2,3,5,7,11,13... и т.д. тоесть не делится на теже простые числа,

тоесть чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа..
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572854
zloyGamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот предельно простой вариант поиска прост. чисел,
т.к. все простые числа в памяти хранить неполучится, то они/результат сохраняеются в файл, и при следующем запуске продолжается поиск с последнего найденного числа,

правда тут размер числа ограничен всего 32 битами, хотя с таким поиском и перебором за этот предел будет сложно уйти.. ))


Код: 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.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
#include <stdio.h>
#include <QFile>
#include <QByteArray>

#define OUT_FILE "simpleNumbers.txt"

bool isSimple(int x)
{//проверка на несколько первых простых чисел
  if(   x %  2   ==  0 
     || x %  3   ==  0 
     || x %  5   ==  0 
     || x %  7   ==  0 
     || x %  11  ==  0 
     || x %  13  ==  0 
     || x %  17  ==  0 
    )
  {
    return  0 ;
  }
  return  1 ;
}

bool isSimpleLongCheck(int x)
{//долгая, бессмысленная и беспощадная проверка )
  int a =  2 ;
  while(a<x)
  {
    if( x % a ==  0  )
    {
      printf(" %d LongCheck\n",a);
      QFile file(OUT_FILE);
      if(file.open(QIODevice::Append))
      {
        file.write(QByteArray::number(x)+" - bad simple\n");
      }
      return  0 ;
    }
    a++;
  }
  return  1 ;
}

void new_simple(int x)
{//запоминаем/записываем новое простое число в файл
  printf("%d isSimple ",x);

  QFile file(OUT_FILE);
  if(file.open(QIODevice::Append))
  {
    file.write(QByteArray::number(x)+"\n");
  }else{
    printf("can't open file for write new_simple number\n");
  }
}

bool isSimpleFileCheck(int x)
{//проверяем делится ли текущее число на какое либо простое число из файла
  QFile file(OUT_FILE);
  if (!file.open(QIODevice::ReadOnly))
  {
    printf("can't open file for SimpleFileCheck\n");
    return  0 ;
  }

  char line[ 2000 ];
  QByteArray data;

  int a =  2 ;
  while(!file.atEnd())
  {
    int k = file.readLine( line, 2000  );
    if(k == - 1 ) continue;
    data = line;
    data.remove(data.size()- 1 , 1 );

    a = data.toInt();
    if(a== 0 )
    {
      //printf("bad number(size:%d): '",data.size());
      //printf(data);
      //printf("'");
      continue;
    }
    if( x % a ==  0  )
    {
      printf(" %d FileCheck",a);
      return  0 ;
    }
  }
  return  1 ;
}


int get_lastSimpleNumber()
{
  QFile file(OUT_FILE);
  if (!file.open(QIODevice::ReadOnly))
  {
    printf("can't open file for get_lastSimpleNumber\n");
    return 17;
  }
  file.seek(file.size()-2000);
  char line[2000];
  QByteArray data;
  int x = 0;
  while(!file.atEnd())
  {
    int k = file.readLine( line,2000 );
    if(k == -1) continue;
    data = line;
    data.remove(data.size()-1,1);

    int a = data.toInt();
    if(a==0)
    {
      continue;
    }
    x = a;
  }
  if(x==0) x=17;
  return x;
}

int main(int argc, char *argv[])
{
    int x = get_lastSimpleNumber();

    QFile file(OUT_FILE);
    if(file.open(QIODevice::Append))
    {
      file.seek(-1);
      QByteArray b;
      b.append("restart search from ");
      b.append(QByteArray::number(x));
      b.append("\n");
      file.write(b);
      file.close();
    }else{
      printf("can't open file for set restart position\n");
    }

    printf("restart search from %d\n",x);

    while(x<0x0FFFFFFF)
    {
      x++;
      bool b = isSimple( x );
      if(b== 1 )
      {
        printf("%d checkSimple ",x);
        b = isSimpleFileCheck(x);
        if(b== 1 ) new_simple(x);
        printf("\n");
      }
    }

    getchar();
    return  0 ;
}
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572883
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
zloyGamer, а зачем ты объявил isSimpleLongCheck но нигде её не используешь?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36572935
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BeastIvгоспода кодеры, а для Borland 3.1 можно вас попросить код написать?
а то задачку хитрую задали... написать программу нахождения n пар простых чисел разница между которыми равна 2, иначе называемых "близнецами", т.е. 3 и 5, 5 и 7, 11 и 13... как пример...

Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать".
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573073
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
zloyGamerпростое число делится только на 1 и на само себя без остатка,
значит не делится на 2,3,5,7,11,13... и т.д. тоесть не делится на теже простые числа,

тоесть чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа..
это допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573089
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нахождение больших простых чисел простым перебором/тестом занимает много м.-времени,
поэтому самое простое, что приходит в голову - это уменьшить число операций цикла за счет фильтра последовательности чисел (Метод от обратного).
Т.е. сразу исключать числа из проверки, которые обладают свойствами не "простого" числа:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
хххх0 - делятся на  2  и  5 , т.е. не простое;
хххх1 - ?
хххх2 - делятся на  2 , т.е. не простое;
хххх3 - ?
хххх4 - делятся на  2 , т.е. не простое;
хххх5 - делятся на  5 , т.е. не простое;
хххх6 - делятся на  2 , т.е. не простое;
хххх8 - делятся на  2 , т.е. не простое;
хххх9 - ?
ххххх - если сумма цифр числа (цифровой корень) =  9 , то число делется на  9 , т.е. не простое;
ххххх - если простая сумма цифр числа делится на  3 , то число делется на  3 , т.е. не простое;
...
и т.п.

Тогда в любой десятке последовательности чисел для теста останется значительно меньше чисел, тем самым можно резко и значительно уменьшить м.-время нахождения массива больших простых чисел.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573102
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AIS,

и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573108
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ПетросъянAIS,

и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля?
Это свойства чисел.
В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5. Это во-первых.
А во-вторых, это одно действие, а пробежаться с тестом на "деление" по всему массиву уже найденных простых чисел - гораздо дольше. ;)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573114
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AISПетросъянAIS,

и как ты предлагаешь сумму цифр к примеру посчитать? или узнать что число делится на 5 не деля?
Это свойства чисел.
В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5. Это во-первых.
А во-вторых, это одно действие, а пробежаться с тестом на "деление" по всему массиву уже найденных простых чисел - гораздо дольше. ;)
ты мне код приведи быстрой проверки делимости на 5
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573115
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AIS
Это свойства чисел.
В частности, если последняя цифра (это видно в примере) равна нулю либо 5, то число делется на 5.
Промах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573125
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Петросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит)
Совсем не обязательно хранить все числа. Но если организовать кеш хотя-бы до тысячи, то можно довольно эффективно отбрасывать уже проверенные, при условии что нагрузка на функцию isSimple будет довольно большой.

В прошлом году в форуме был довольно плотный тред на эту тему и если вы не поленитесь то найдете немало интересного на тему решета Эратосфена и оптимального хранения чисел в кеше.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573128
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Петросъян ,
а вообще - это была идея/предложение/совет/мысль в слух/направление поиска решения.
Я так полагаю, что это можно назвать и "алгоритмом".
А создавать далее скрипт, как то не хочется.
Gluk (Kazan)Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать".
Золотые слова.


maytonПромах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее.
Промах, согласен, проглядел где-то что "хранится в ДВОИЧНОЙ". ;)
А в остальном не согласен.
Если с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573134
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПетросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит)
Совсем не обязательно хранить все числа. Но если организовать кеш хотя-бы до тысячи, то можно довольно эффективно отбрасывать уже проверенные, при условии что нагрузка на функцию isSimple будет довольно большой.

В прошлом году в форуме был довольно плотный тред на эту тему и если вы не поленитесь то найдете немало интересного на тему решета Эратосфена и оптимального хранения чисел в кеше.
в общем случае выигрыш этого улучшательства будет стремиться к бесконечносит
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573135
Фотография Петросъян
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AIS Петросъян ,
а вообще - это была идея/предложение/совет/мысль в слух/направление поиска решения.
Я так полагаю, что это можно назвать и "алгоритмом".
А создавать далее скрипт, как то не хочется.
Gluk (Kazan)Звучит примерно как "ану-ка, холопы, настреляйте мне дичи из этого мушкета. Не пановское это дело по лесам бегать".
Золотые слова.


maytonПромах. Ты повторяешь мои ошибки. Признаки делимости на 3,5,9 и т.д. для ДЕСЯТИЧНЫХ чисел не имеют никакого практического полезного эффекта если проверяемое число хранится в ДВОИЧНОЙ. Проверка на операцию '%' будет эффективнее.
Промах, согласен, проглядел где-то что "хранится в ДВОИЧНОЙ". ;)
А в остальном не согласен.
Если с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет.
тип оф зи дей: в компе все в двоичной.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573143
AIS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Петросъян...в компе все в двоичной.
А я так глубоко не заглядываю. ;)
Но полагаю, что с двоичными по предложенному методу, тоже можно получить эффект в сравнении с простым перебором всех значений.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573147
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AISЕсли с десятичными числами можно достигнуть необходимого эффекта (скорость получения результата), то уже из массива простых чисел в десятичном виде перевести в двоичный - много времени и сил не займет.
Эта мысль заведёт тебя в тупик. Сама по себе операция перехода между базисами имеет вычислительную сложность. А производительность для алгоритмов prime-детектирования и факторизации - это самое главное.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36573176
zloyGamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonzloyGamer, а зачем ты объявил isSimpleLongCheck но нигде её не используешь?
isSimpleLongCheck - проверяет делится ли число X на любое из чисел от 2 до X-1 простым перебором,
если так проверять каждое число то на поиск уйдет довольно много времени., но этйо функцией я проверял свою дествительно ли: zloyGamer"чтобы найти следующее простое число, - надо просто проверить неделится ли оно на все предыдущие найденные прост. числа.."


Петросъянэто допер, но эти числа надо тогда хранить что не правильно (во всяком случае мне не подходит) нет, иначе алгоритмы определения/поиска будут тратить на этоже дело гораздо больше времени, поэтому самое оптимальное хранить эти числа и с ними сравнивать,
вот только как их хранить чтоб потом быстро выбирать/добавлять, - проблема тока в реализации.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36586989
zhenga
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
zloyGamer,

A ut kuda vziat QFile i QByteArray. U menia bez nix oshibki vydayut
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #36587429
Дональдак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
zhenga, он использовал QT framework.
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
Алгоритм нахождения простых чисел
    #37511500
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

привет. можете дать программу нахождения самого большого числа?
мой msergeyj@mail.ru буду благодарен=)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511529
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
серегй,

Вообще самого большого простого?
Как бэ никто не доказал еще, что ряд простых - конечен...
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511558
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сергей, самое большое простое число известное науке входит
в множество простых чисел Мерсена. Ищите в wiki там много
материала.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511632
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AndreTM,

не самое большое, а большое простое число которое можно найти на простом пк.
мне бы алгоритм нахождения на с++
кто нибудь помогите
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511637
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

вы там написали что можете дать программу для нахождения "самого большого простого числа"
если можно я бы хотел посмотреть=)
msergeyj@mail.ru это моя почта.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511646
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не мог я такого написать.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37511674
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
zloyGamer,

хай zloyGamer а вы что думайте?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37512136
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
серегйAndreTM,

не самое большое, а большое простое число которое можно найти на простом пк.
Вообще-то, последнее "самое большое простое Мерсенна" и было найдено "на простом ПК" два года назад. http://mersenne.org

Даже если вы подразумеваете, что-то типа "надо найти на простом (?) ПК наибольшее возможное простое с помощью " решета Эратосфена ", то и в этом случае необходимо привести хотя бы характеристики этого вашего ПК, а также ожидаемое возможное время на расчет...
В противном случае, ваш вопрос не имеет смысла.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37512409
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AndreTM,

ну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513130
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
серегйну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться.
2**31-1 устроит?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513133
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропил,

угу
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513271
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513287
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
серегйAndreTM,

ну обычный двухядерный ноут=) мне главное чтоб было на диапазоне 32. лонг инт кажеться.
В принципе, эратосфенить можно до бесконечности при любой разрядности процессора. Разве что, закончится оперативная память.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513392
tanglir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AndreTMсерегй,

Вообще самого большого простого?
Как бэ никто не доказал еще, что ряд простых - конечен...Мало того, как бэ давно доказано, что он бесконечен, разве нет?..
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513420
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну, если Сергей поставит себе на борт 8Г памяти,
это будет

8Г = 8192М = 8388608K = 8589934592 байт = 68 719 476 736 бит информации.

Это же число будет задавать диапазон для метода Эратосфена.

Для простоты будем считать что ОС не в счёт.

Самое (почти) большое число Мерсена (на 6 ноября 2011 г)
по данным wiki:



там же пишут что это число имеет 12 978 189 десятичных разрядов против
наших 11 разрядов эратосфена на типовой рабочей станции.

Тоесть "эратосфенить" для поиска наибольшего простого
числа не имеет смысла. Имеет смысл генерить числа
Мерсена и делать максимально-быстрые тесты на простоту.

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

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

Поэтому поиск максимально большого простого числа в диапазоне
чисел или просто поиск макс. большого простого числа известного
науке
- это разные задачи.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37513981
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

учту=)
еще кто что думает?
у кого ни будь есть примеры программы?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37514122
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
хто та из великих доказал еще в школе, что самого большого не существует :-)
доказательство тривиально, могу привести :-)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37514247
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aklin...могу привести :-)
Давай.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37515372
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ShSerge,

я не ищу именно самое большое число а то число кторое можно найти на моем ноуте используя С++
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37515380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Точную ссылку не помню но посмотри отсюдова 7164978
назад и вперёд. Там много исходников. Почти работают на
обычных раб-станциях с 1Г оперативки.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37515451
серегй
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

ого круто=) кое че нашел!
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37747441
Denis_m1st
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
qwedfgСуществует-ли такой ? Решение этого задания есть тут: Задачи на числа. Решение. Покритикуйте. (часть №1)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37749438
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Удивительно живучая тема, судя по количеству поднятий через интервал более года.
Простые числа волнуют умы и сердца молодых программеров.
:)


серегйне самое большое, а большое простое число которое можно найти на простом пк.
серегй,
если не секрет, а зачем оно тебе, и что ты с ним будешь делать?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792182
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
function getPrimesBefore(number)
{
	if(number<2) return [];
	if(number==2) return [2];
	var primes=[2];
	for(var itest=3;itest<=number;itest+=2)
	{
		var margin=Math.floor(Math.sqrt(itest))+1;
		var iprime=!primes.some(function(pr){return !(itest%pr)});
		if(iprime) primes.push(itest);
	}
	return primes;
}



Так оно будет на ECMAScript 5.
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792184
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, нафига я считал margin - вообще непонятно. Выбрасываем.
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function getPrimesBefore(number)
{
	if(number<2) return [];
	if(number==2) return [2];
	var primes=[2];
	for(var itest=3;itest<=number;itest+=2)
	{
		var iprime=!primes.some(function(pr){return !(itest%pr)});
		if(iprime) primes.push(itest);
	}
	return primes;
}
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792203
kDnZP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Division X, не проблема найти простые числа, проблема найти их быстро))). Правильный алгоритм должен начинаться со слова "решето" ИМХО ;)
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792206
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kDnZPDivision X, не проблема найти простые числа, проблема найти их быстро))). Правильный алгоритм должен начинаться со слова "решето" ИМХО ;)
Ну а это что, по-твоему?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792207
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Надеюсь, не надо расшифровывать, что такое some и push?
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37792213
Division X
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kDnZPПравильный алгоритм должен начинаться со слова "решето" ИМХО ;)
kDnZP-compatible version:
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
function getPrimesBefore(number)
{ //РЕШЕТО
	if(number<2) return [];
	if(number==2) return [2];
	var primes=[2];
	for(var itest=3;itest<=number;itest+=2)
		if(!primes.some(function(pr){return !(itest%pr)}))
			primes.push(itest);
	return primes;
}
...
Рейтинг: 0 / 0
Алгоритм нахождения простых чисел
    #37918600
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Ну да
"The Most Unique Number is always the prime" я бы перевел по-своему: "В чем сила, брат?"
...
Рейтинг: 0 / 0
84 сообщений из 84, показаны все 4 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм нахождения простых чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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