Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 29 30 [31] 32   вперед  Ctrl
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1348
kealon(Ruslan)
Barlone,

алгоритм Полларда как раз использует СОК
А это который? Есть как минимум два разных алгоритма, связанных с Поллардом:
1. Многократное вычисление x = f(x) в поисках циклического повторения (где f - полином от x).
2. Возведение в степень 2*2*…*2*3*3*…*5*… в ожидании получения 1 по модулю одного из сомножителей.
И в обоих методах все вычисления ведутся по модулю факторизуемого числа. Где там вычисления по другим модулям?
27 мар 19, 20:31    [21845440]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Barlone,

хм, найти не могу, в котором N-1 пытаются разложить

но мне кажется это тупиковый путь, разлагать надо N+1
27 мар 19, 23:57    [21845539]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Наверное, интересно обсудить ещё одну проблему.

Как известно, количество простых чисел , начиная с 1 и до N, равно N/ln(N). И соотношение простых и составных чисел определяется числом 1/ln(N).

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

Каждая из этих последовательностей начинается с определённого числа А и имеет бесконечное количество элементов.

На отдельном отрезке от А до М количество чисел отдельной последовательности будет равно К.

Тогда такая последовательность имеет место быть интересной, если количество 1/ln(К) будет больше 1/ln(М - А)
28 мар 19, 16:28    [21846328]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
Gennadiy Usov
такая последовательность имеет место быть интересной, если количество 1/ln(К) будет больше 1/ln(М - А)

Последовательность интересна, если в ней m/ln(N) вместо 1/ln(N), m>1, N - длинна последовательности. А что вы выше написали - я не понял.

Ну и до кучи, пока ваша заслуга видится лишь в предложении переносимого шаблона (с вариациями), который дёшево получать, но и польза от него не очень большая (хотя и важная для редких случаев). Всё остальное - плохо оформленные мысли вслух. Если и дальше мысли будут не очень связными, то я не уверен, что вас кто-то поймёт, и уж тем более, оценит заслуги.
28 мар 19, 18:59    [21846536]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
alex55555
Gennadiy Usov
такая последовательность имеет место быть интересной, если количество 1/ln(К) будет больше 1/ln(М - А)
Последовательность интересна, если в ней m/ln(N) вместо 1/ln(N), m>1, N - длинна последовательности. А что вы выше написали - я не понял.
Вы как всегда всё перепутали!

Это есть за Вами...

Я говорил о соотношении всех чисел в последовательности и простых чисел в последовательности, а Вы говорите о количестве простых чисел.
Это две разные вещи.
28 мар 19, 19:11    [21846547]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
Gennadiy Usov
Это две разные вещи.

Примерно на столько же разные, как х и 1/х.
29 мар 19, 13:49    [21847028]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
вот кстати вопрос, есть разложение числа на простые множители p1^a1 * p2^a2 ....
какой оптимальный алгоритм итератора, который получает все делители числа?
29 мар 19, 15:48    [21847263]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Если представить в виде произведения (p1 * p1 ..... * p1) * (p2 * p2 ..... p2) тогда это близко
к генерации сочетаний КМК множителей.
29 мар 19, 16:29    [21847322]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
mayton,

если бы a1, a2, a3 ... были бы единицами то да, а вот когда не 1, большая фигня выходит
29 мар 19, 17:03    [21847375]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Тут должно быть что-то наподобие генерации укладок рюкзака.
29 мар 19, 17:04    [21847381]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
mayton,

усложняешь, в тупую я знаю как сделать - сложение с перебросом по a(i) основаниям
всего (a1+1) * (a2+1)*... вариантов будет

а вот как это сделать эффективно
29 мар 19, 17:11    [21847390]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Хочешь получить сочетания 2х множителей из всех? Или все множители из всех?
29 мар 19, 17:22    [21847401]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
mayton,

хочу получить все делители числа из его разложения, включая 1 и само число
29 мар 19, 17:24    [21847404]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
kealon(Ruslan)
вот кстати вопрос, есть разложение числа на простые множители p1^a1 * p2^a2 ....
какой оптимальный алгоритм итератора, который получает все делители числа?

Степень понижает величину простого числа. И если известно, что произведение равно, скажем, 21024, то даже две степени по 2 приведут уже к числу 2128. То есть придётся брать степени много больше 1024 с соответствующим проседанием производительности.

А если без степеней, то для двух чисел степень (до которой нужно проверять) будет 512, для трёх - 333 и т.д. Непонятно - зачем там вообще степени.
29 мар 19, 17:57    [21847461]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
kealon(Ruslan)
вот кстати вопрос, есть разложение числа на простые множители p1^a1 * p2^a2 ....
какой оптимальный алгоритм итератора, который получает все делители числа?
Я не думал, что для каждого сочетания множителей необходим отдельный алгоритм итератора.

А если серьёзно, то множителей много, и есть большая вероятность, что множители не будут большими.
А здесь годится обычный алгоритм проверки на делимость мелких множителей с последующим делением исходного числа на эти множители.
29 мар 19, 18:06    [21847475]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1348
kealon(Ruslan)
mayton,

если бы a1, a2, a3 ... были бы единицами то да, а вот когда не 1, большая фигня выходит
Есть k разных множителей. Заводишь массив из k элементов, заполняешь 0. Это будут степени. Изначально p1^0*p2^0*…. = 1.
В цикле увеличиваешь младший элемент, если он стал больше a1, обнуляешь и увеличиваешь следующий.
30 мар 19, 07:37    [21847684]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Barlone,

21847390

я проще нашёл способ
31 мар 19, 09:54    [21848152]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
kealon(Ruslan)
mayton,
если бы a1, a2, a3 ... были бы единицами то да, а вот когда не 1, большая фигня выходит
Есть k разных множителей. Заводишь массив из k элементов, заполняешь 0. Это будут степени. Изначально p1^0*p2^0*…. = 1.
В цикле увеличиваешь младший элемент, если он стал больше a1, обнуляешь и увеличиваешь следующий.
А что, известны a1, a2, a3 ...? Известно их количество?

А если неизвестны, то как сформируется массив?
31 мар 19, 10:05    [21848157]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov
Однако у меня только 15 значащих цифр - это предел по поиску простых чисел.
Кстати, есть ещё одна последовательность: 3,5 произведения простых чисел минус 4:
17, 101, нет, 8081, нет, 1786781, нет, нет, 22543926301, нет, нет, 960985588457891
Далее размер ячейки не позволяет
А попробуйте на этом сайте https://ideone.com/ ввести маленький кусок программы на языке Питон.
for x in range(1, 8):
	print 2 ** x
Только внизу там в выпадающем меню где выбор языков надо переключить на "Python"

Все-таки попробовал применить сайт для расчетов.

Однако, величина числа на сайте не может превышать числа (2^460)^2.

А что есть для чисел, больших (2^460)^2?
10 июл 19, 11:02    [21924029]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Gennadiy Usov,

Мозг всё зависит от операций, например, есть системы счисления, где для ряда операций можно считать результат параллельно - СОК
10 июл 19, 11:30    [21924051]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov
mayton
пропущено...
А попробуйте на этом сайте https://ideone.com/ ввести маленький кусок программы на языке Питон.
for x in range(1, 8):
	print 2 ** x
Только внизу там в выпадающем меню где выбор языков надо переключить на "Python"

Все-таки попробовал применить сайт для расчетов.

Однако, величина числа на сайте не может превышать числа (2^460)^2.

А что есть для чисел, больших (2^460)^2?

Я подозреваю что создатели сайта искусственно ограничили Время сеанса одной пользовательской сессии.
Тоесть дело не в разрядности а в регулировке ресурсов.

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

Или установи себе инетрпретатор Python.
10 июл 19, 11:39    [21924058]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov
Однако, величина числа на сайте не может превышать числа (2^460)^2.
А что есть для чисел, больших (2^460)^2?

Я подозреваю что создатели сайта искусственно ограничили Время сеанса одной пользовательской сессии.
Тоесть дело не в разрядности а в регулировке ресурсов.
Это чтобы хитрые пользователи не майнили и не решали криптографических задач. Но нам решать то не надо.
Если просто перемножить - то кидай сюда свой кусок кода. Энтузисаты попробуют выполнить.
Или установи себе инетрпретатор Python.
Как всегда, поторопился.

Ошибка не по числу, а по количеству выводимой информации.

Так что, процесс поиска чисел Fp/3 продолжается...
10 июл 19, 13:20    [21924150]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
http://mech.math.msu.su/~shvetz/54/inf/perl-problems/chPrimes_sIdeas.xhtml

В данном сообщении приводится «колёсный метод» поиска простых чисел.

Данное определение соответствует поиску простых чисел, начиная с 1.
Идет постепенный ход колеса по числовому ряду.

Это то же самое, что и рассматриваемый в данном топике принцип «рамки» в виде блока чисел.

«Рамка» может накладываться в произвольном месте числового ряда,
начиная с определённого числа, которое кратно размеру рамки плюс 1.

В приведённой выше публикации показываются достоинства «колёсного метода» или «рамки»
по скорости определения небольших делителей, «образующих очередную рамку».

Минус – размер «рамки».

Поэтому можно рассматривать совмещение «рамки»
и продолжение деления определяемого числа на следующие простые числа.
29 июл 19, 09:26    [21936585]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Сделал небольшую программу на Python для определения с помощью «рамки» чисел, которые не делятся на 2, 3, 5:
my_list = [30, 8, 1, 7, 11, 13, 17, 19, 23, 29]						
print my_list						
ind = 0						
nm = my_list [0]						
em = my_list [ 1] - 1						
b3 = pow(2, 1024) - 1 						
b2 = pow(b3, 1, nm) 						
b = b3 - b2 + 1						
b1 = b + 200000						
while b <= b1:						
	e = 1					
	e1 = e + em					
	while e <= e1:					
		c = (b-1) * nm +my_list [e + 1]				
		ind +=1				
		#print c, b,e,  ind				
		e += 1				
	b += 1					
print ind						
						
Успешно #stdin #stdout 0.68s 7288KB						
[30, 8, 1, 7, 11, 13, 17, 19, 23, 29]						
1600008	
Нашел много таких чисел (c), которые следуют за 2^1024 (для примера)
29 июл 19, 19:05    [21937194]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
На сайте https://ideone.com/ всё проходит нормально.
Однако есть ограничение - 5 сек.
mayton
Или установи себе инетрпретатор Python.
Попробовал установить
Python 3.7.4 (tags/v3.7.4:e09359112e, Jul 8 2019, 19:29:22) [MSC v.1916 32 bit (Intel)] on win32

Оказалось, что степень 50 обрабатывает нормально, а степени больше 100 ( в отличии от https://ideone.com/) обрабатывает с ошибками.

Может быть есть более надёжный инетрпретатор Python?
5 авг 19, 11:22    [21941950]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 29 30 [31] 32   вперед  Ctrl
Все форумы / Программирование Ответить