*[list]

?

http://paste.org.ru/?julhi8 можете подсказать почему ошибка?

Что это? Какой дистрибутив? Как питон ставил?

как минимум предлагаю предрассчитать корень из лимита

Честно говоря я в Аткине мало что понимаю, с Эратосфеном еще могу разобраться

я тоже

но корень из лимита, очевидно, не изменяется по ходу алгоритма

вообще я не удивлён, что ты не видишь асимптотической разницы в (log log n)^2 на таком n

вообще я не удивлён, что ты не видишь асимптотической разницы в (log log n)^2 на таком n

я вообще не понимаю о чем ты говоришь. вижу только ущемленное ЧСВ.

На кой хер распаковывать лист в лист?

я вообще не понимаю о чем ты говоришь. вижу только ущемленное ЧСВ.

ЧСВ? што?

я посмотрел асимптотики алгоритмов, которые ты сравниваешь, в википедии и увидел разницу в (log log n)^2

я вообще не понимаю о чем ты говоришь. вижу только ущемленное ЧСВ.

Про асимптотическую сложность. Кхе. При чем тут чсв

На кой хер распаковывать лист в лист?

понятия не имею, я только начал питон изучать

с учётом того, что второй алгоритм сложнее, очевидно, он начнёт выигрывать только на достаточно больших n

вывод: твой миллион - не достаточно большое n

уже интереснее

а скинь код текстом

https://habr.com/post/122538/

import math def sieveOfAtkin(limit): P = [2,3] sieve=[False]*(limit+1) for x in range(1,int(math.sqrt(limit))+1): for y in range(1,int(math.sqrt(limit))+1): n = 4*x**2 + y**2 if n<=limit and (n%12==1 or n%12==5): sieve[n] = not sieve[n] n = 3*x**2+y**2 if n<= limit and n%12==7: sieve[n] = not sieve[n] n = 3*x**2 - y**2 if x>y and n<=limit and n%12==11: sieve[n] = not sieve[n] for x in range(5,int(math.sqrt(limit))): if sieve[x]: for y in range(x**2,limit+1,x**2): sieve[y] = False for p in range(5,limit): if sieve[p] : P.append(p) return P sieve=sieveOfAtkin(10000000) #print (sieve) print (len(sieve))

n = 10000000 # число, до которого хотим найти простые числа numbers = list(range(2, n + 1)) for number in numbers: if number != 0: for candidate in range(number**2, n+1, number): numbers[candidate-2] = 0 #print(*list(filter(lambda x: x != 0, numbers))) # выводим простые числа sieve=[*list(filter(lambda x: x != 0, numbers))] print (len(sieve))

Ещё раз

Сложный питон

Вы из с++?

вычитал, что Аткин быстрее Эратосфена, но из тех алгоритмов, что я нашел выходит обратное...

Я бы предложил ещё вместо аппенда в P сделать generator expresdion

import math def sieveOfAtkin(limit): P = [2,3] sieve=[False]*(limit+1) for x in range(1,int(math.sqrt(limit))+1): for y in range(1,int(math.sqrt(limit))+1): n = 4*x**2 + y**2 if n<=limit and (n%12==1 or n%12==5): sieve[n] = not sieve[n] n = 3*x**2+y**2 if n<= limit and n%12==7: sieve[n] = not sieve[n] n = 3*x**2 - y**2 if x>y and n<=limit and n%12==11: sieve[n] = not sieve[n] for x in range(5,int(math.sqrt(limit))): if sieve[x]: for y in range(x**2,limit+1,x**2): sieve[y] = False for p in range(5,limit): if sieve[p] : P.append(p) return P sieve=sieveOfAtkin(10000000) #print (sieve) print (len(sieve))

кстати, какая у тебя версия питона?

кстати, какая у тебя версия питона?

хороший вопрос...

3.7

Аткина нашел в интернете, Эратосфена в другой группе помогли найти. в нем я только на #63 сменил number*2 на number**2

И реально 1. Предпосчитай корень 2. Посчитай x**2, y**2 один раз за цикл 3. Убери аппенд в список

И проверь ещё раз

Аткина нашел в интернете, Эратосфена в другой группе помогли найти. в нем я только на #63 сменил number*2 на number**2

короч, Аткин более эффективен только на сильно больших n.

я взял твой код и у меня отношение времени работы Аткина к времени работы Эратосфена уменьшается с ростом n. но медленно.

вероятно, на достаточно большом n Аткин в итоге победит. но оперативки, чтобы дождаться этого, может не хватить)

вероятно, на достаточно большом n Аткин в итоге победит. но оперативки, чтобы дождаться этого, может не хватить)

понятно, осталось переварить как вообще код работает...

Спасибо

да там теория чисел обычная

да там теория чисел обычная

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

питон — плохой язык для числодробилок

эффективные алгоритмы тут не так эффективны из-за накладных расходов (проверки индексов, например)

лучше изучать алгоритмы, для которых достаточно встроенных структур данных (динамический массив, хэштаблица, куча)

лучше изучать алгоритмы, для которых достаточно встроенных структур данных (динамический массив, хэштаблица, куча)

Окей гугл...))

короч, изучай лучше структуры данных)

короч, изучай лучше структуры данных)

?

Си

Linked list, tree

На этом мои знания всё

?

недурно

разворачивать односвязный список умеешь? )

Мы на собеседованиях обычно просили человека как можно больше способов разворота списка предложить

?

я только один эффективный себе представляю

Эффективность не требуется

Вот зачем так задрачивать

разворачивать односвязный список умеешь? )

хе-хе, в этом нет ничего сложного: рисуешь односвязный список, меняешь направление строелочек))

Эффективность не требуется

ну бля

ну вот бля

что за вопросы

Мы на собеседованиях обычно просили человека как можно больше способов разворота списка предложить

чтобы потом на работе тоже тем же заниматься, видимо

сможет ли чувак придумать разворачивание списка за O(n! n)?

хе-хе, в этом нет ничего сложного: рисуешь односвязный список, меняешь направление строелочек))

ну да)

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

но некоторые не справляются

чтобы потом на работе тоже тем же заниматься, видимо

Ага. Чтобы потом если эффективный из-за каких-то ограничений не реализуем человек мог что-то придумать

ERROR: S client not available

что за бред

можно же сразу давать задачки с ограничениями

скилл решать задачки с ограничениями у всех хороших разрабов есть

а скилл придумывать заведомо хуёвые решения — это как-то уж больно специфично

Вопрос не в списке. А том, чтобы человек мог предложить альтернативное решение тому что уже знает

можно же просто давать задачки, которые человек ещё не знает)

Да мы и перестали спрашивать про список

список — это хорошая задачка не на алгоритмы, а именно на код

Народ как правило даже цифры в числе переставить не может

Да мы и перестали спрашивать про список

про графы спрашиваете?

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

Народ как правило даже цифры в числе переставить не может

?

Один кандидат пытался гуглить какая есть библиотека для взятия остатка от деления

? ? ?

oh my

это был я

Linked list, tree

rb tree?

это был я

Ты на свифте пишешь?

о, так это был мобильный разработчик

они ребята интересные

Ага

Я в основном таких собеседовал

у них ограничние на мемы и cpu

они ребята интересные

чем??

ааа

и акб

у нас в компании тоже проблемы с наймом мобильных разработчиков

мало кто скрининг даже проходит

работать в вашей компании честь?

работать в вашей компании честь?

а то!

у нас в компании тоже проблемы с наймом мобильных разработчиков

Может мне надо было к вам на мобилки? :)))

Может мне надо было к вам на мобилки? :)))

А ты уверен, что ты бы прошёл? ? Там реально жёстко отбирают, да ещё и программировать надо будет на Objective-C, а не на свифте