powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм нахождения простых чисел
25 сообщений из 84, страница 2 из 4
Алгоритм нахождения простых чисел
    #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
25 сообщений из 84, страница 2 из 4
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм нахождения простых чисел
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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