Пояснення необхідне для суми простих нижче n чисел

Сьогодні я вирішив проблему, зазначену в Project Euler , це проблема № 10 , і мені знадобилося 7 годин для моєї програми python, щоб показати результат. Але в цьому самому форумі людина, названа lassevk розмістила рішення для цього, і вона зайняла лише 4 сек . І це не можливо для мене, щоб розмістити це питання в цьому форумі, тому що це не дискусійний форум. Отже, подумайте про це, якщо ви хочете відзначити це питання як неконструктивний.

marked = [0] * 2000000
value = 3
s = 2
while value < 2000000:
    if marked[value] == 0:
        s += value
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2
print s

Якщо хтось розуміє цей код, будь ласка, поясніть його якомога простіше.

Це мій код, який вимагав 7 годин для обчислення (я думаю, що я також використовував ту ж логіку техніки сито Ератосфена, про яку йшлося у відповідях нижче):

import time
start = time.clock()

total = 0
limit = 2000000
KnownPrime = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
                  53, 59, 61, 67, 71])
KnownPrime.update(set([73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
                       131, 137, 139, 149, 151, 157, 163, 167, 173]))
suspected = set(range(2, limit+1)) # list of suspected prime numbers
for p in KnownPrime:
    if p <= limit:
        total += p
        suspected.difference_update(set(range(p, limit+1, p)))

for i in suspected:
    k = i/2
    if k % 2 == 0: k += 1
    PrimeCheck = set(range(k, 2, -2))
    PrimeCheck.difference_update(KnownPrime)
    for j in PrimeCheck:
        if i % j == 0:
            break
    if i % j:
        total += i

print time.clock() - start
print total

Отже, чи може хто-небудь сказати мені, чому це зайняло багато часу.

Нарешті, я зробив це тут моїм реорганізованим кодом. Тепер він може показувати результат за 2 сек.

import math
import __builtin__

sum = __builtin__.sum

def is_prime(num):
    if num < 2: return False
    if num == 2: return True
    if num % 2 == 0: return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0: return False
    return True

def sum_prime(num):
    if num < 2: return 0
    sum_p = 2
    core_primes = []
    suspected = set(range(3, num + 1, 2))
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if is_prime(i): core_primes.append(i)
    for p in core_primes:
        sum_p += p
        suspected.difference_update(set(range(p, num + 1, p)))
    return sum(suspected) + sum_p

print sum_prime(2000000)

Ось візуалізація .

1
@WillNess Я думаю, що я можу зробити це лише за допомогою функції is_prime ()
додано Автор bkmagnetron, джерело
@WillNess Я думаю, що я можу зробити це лише за допомогою функції is_prime ()
додано Автор bkmagnetron, джерело
@WillNess ой .. так .. так що я дійсно зробив це на мою власну (не знаючи про сито), за винятком того, що sqrt (). : D
додано Автор bkmagnetron, джерело
@WillNess ой .. так .. так що я дійсно зробив це на мою власну (не знаючи про сито), за винятком того, що sqrt (). : D
додано Автор bkmagnetron, джерело
@WillNess ой .. так .. так що я дійсно зробив це на мою власну (не знаючи про сито), за винятком того, що sqrt (). : D
додано Автор bkmagnetron, джерело
@WillNess: O сума для друку (prime_list3x (2000000)) + 2 Чи можу я знати, що ви маєте досвід програмування? Єдиний досвід може дати таку велику кількість знань про програму, або я повинен був робити якісь додаткові продукти для того, щоб бути програмістом, як ви? Як я можу навчитися аналізувати код, як ви?
додано Автор bkmagnetron, джерело
@WillNess ох .. але .. він був відредагований 12 разів до цих пір будь-яким чином я буду слідувати за вами поради і ще раз спасибі :)
додано Автор bkmagnetron, джерело
@WillNess ох .. але .. він був відредагований 12 разів до цих пір будь-яким чином я буду слідувати за вами поради і ще раз спасибі :)
додано Автор bkmagnetron, джерело
@WillNess ох .. але .. він був відредагований 12 разів до цих пір будь-яким чином я буду слідувати за вами поради і ще раз спасибі :)
додано Автор bkmagnetron, джерело
@WillNess: O сума для друку (prime_list3x (2000000)) + 2 Чи можу я знати, що ви маєте досвід програмування? Єдиний досвід може дати таку велику кількість знань про програму, або я повинен був робити якісь додаткові продукти для того, щоб бути програмістом, як ви? Як я можу навчитися аналізувати код, як ви?
додано Автор bkmagnetron, джерело
@WillNess: O сума для друку (prime_list3x (2000000)) + 2 Чи можу я знати, що ви маєте досвід програмування? Єдиний досвід може дати таку велику кількість знань про програму, або я повинен був робити якісь додаткові продукти для того, щоб бути програмістом, як ви? Як я можу навчитися аналізувати код, як ви?
додано Автор bkmagnetron, джерело
@WillNess Подяки :)
додано Автор bkmagnetron, джерело
@WillNess Подяки :)
додано Автор bkmagnetron, джерело
@WillNess Подяки :)
додано Автор bkmagnetron, джерело
Вашим рішенням є не сито Ератосфена. Ваше використання оператора по модулю видаляє його; це пробний поділ. Як вказує @rmunn, пробний поділ є алгоритмом O (n ^ 2), але сито Ератосфена - це тільки O (n log log n), що майже лінійно.
додано Автор user448810, джерело
Вашим рішенням є не сито Ератосфена. Ваше використання оператора по модулю видаляє його; це пробний поділ. Як вказує @rmunn, пробний поділ є алгоритмом O (n ^ 2), але сито Ератосфена - це тільки O (n log log n), що майже лінійно.
додано Автор user448810, джерело
Вашим рішенням є не сито Ератосфена. Ваше використання оператора по модулю видаляє його; це пробний поділ. Як вказує @rmunn, пробний поділ є алгоритмом O (n ^ 2), але сито Ератосфена - це тільки O (n log log n), що майже лінійно.
додано Автор user448810, джерело
Я не 100% undestand це, але це дуже, дуже розумне рішення. Все, що я можу сказати вам, що значення - це 3, тому що це найменше просте число і s = 2 , тому що ми не можемо забути, що 2 є простим числом
додано Автор TerryA, джерело
Я не 100% undestand це, але це дуже, дуже розумне рішення. Все, що я можу сказати вам, що значення - це 3, тому що це найменше просте число і s = 2 , тому що ми не можемо забути, що 2 є простим числом
додано Автор TerryA, джерело
Я не 100% undestand це, але це дуже, дуже розумне рішення. Все, що я можу сказати вам, що значення - це 3, тому що це найменше просте число і s = 2 , тому що ми не можемо забути, що 2 є простим числом
додано Автор TerryA, джерело
Ви можете замінити внутрішній цикл while на , позначений [i :: i] = [1] * ((2000000-1)/i) для приємного прискорення
додано Автор John La Rooy, джерело
Ви можете замінити внутрішній цикл while на , позначений [i :: i] = [1] * ((2000000-1)/i) для приємного прискорення
додано Автор John La Rooy, джерело
ideone.com/c566K7 : змініть sum_prime (num) , щоб зібрати прості числа в список, а не підсумовувати їх. Потім використовуйте його як list_primes (int (math.sqrt (num)) + 1) для обчислення "основних" чисел для себе. :)
додано Автор Will Ness, джерело
ideone.com/c566K7 : змініть sum_prime (num) , щоб зібрати прості числа в список, а не підсумовувати їх. Потім використовуйте його як list_primes (int (math.sqrt (num)) + 1) для обчислення "основних" чисел для себе. :)
додано Автор Will Ness, джерело
Більше декількох років. :) Я також працював з Lisp; Випробувана схема, Пролог ... Книга SICP - це чудове читання, Мистецтво Прологу ... Але я дійсно посередній програміст, це все досить елементарні речі; рекурсія є базовою технікою. Алгоритми елементарних простих чисел, як сито або ТД - це досить прості дрібниці ... Щасливі траси! :)
додано Автор Will Ness, джерело
Більше декількох років. :) Я також працював з Lisp; Випробувана схема, Пролог ... Книга SICP - це чудове читання, Мистецтво Прологу ... Але я дійсно посередній програміст, це все досить елементарні речі; рекурсія є базовою технікою. Алгоритми елементарних простих чисел, як сито або ТД - це досить прості дрібниці ... Щасливі траси! :)
додано Автор Will Ness, джерело
ideone.com/c566K7 : змініть sum_prime (num) , щоб зібрати прості числа в список, а не підсумовувати їх. Потім використовуйте його як list_primes (int (math.sqrt (num)) + 1) для обчислення "основних" чисел для себе. :)
додано Автор Will Ness, джерело
Більше декількох років. :) Я також працював з Lisp; Випробувана схема, Пролог ... Книга SICP - це чудове читання, Мистецтво Прологу ... Але я дійсно посередній програміст, це все досить елементарні речі; рекурсія є базовою технікою. Алгоритми елементарних простих чисел, як сито або ТД - це досить прості дрібниці ... Щасливі траси! :)
додано Автор Will Ness, джерело
Ласкаво просимо. у всякому разі, чому ваш початковий код був настільки повільним (оскільки ніхто не відповів на це): k = i/2 є винуватцем. Змінивши його на k = int (math.sqrt (i) + 1) , слід зняти час виконання у діапазоні хвилин . І так, як ви, напевно, знаєте зараз, початкове видалення 40 простих чисел і їх кратні було зроблено методом сита Ерса.
додано Автор Will Ness, джерело
@rmunn мій вищевказаний тест емпірично підтримує те, що a.difference_update (b) працює в O (len (b)) . Отже, ні, він не виконується в O (N) , де N = len (a) , який необхідний, щоб зробити загальний час квадратичним. Набори добре працюють тут, і остаточний код оператора виконується в O (n log (log n)) , на наборах. Наборів тут не було.
додано Автор Will Ness, джерело
загалом, ви повинні використовувати для i в діапазоні (3, int (math.sqrt (n)) + 1, 2): у вашому def is_prime (n): . окрім цього, ви отримали це! :) До речі, ви могли б використовувати метод сита, щоб знайти список основних простих елементів, а не пробний поділ; але це не впливає на загальну складність. Навіть ваш субоптимальний пробний розділ не впливає на загальну складність часу - він сприяє O ((sqrt (n)) ^ 2) (і оптимальному, O() (sqrt (n)) ^ 1.5) ) у загальний O (n log log n) (це, якщо множини видаляють кожен елемент у часі O (1) , як це дійсно можна можна очікувати від структури даних на основі словника).
додано Автор Will Ness, джерело
загалом, ви повинні використовувати для i в діапазоні (3, int (math.sqrt (n)) + 1, 2): у вашому def is_prime (n): . окрім цього, ви отримали це! :) До речі, ви могли б використовувати метод сита, щоб знайти список основних простих елементів, а не пробний поділ; але це не впливає на загальну складність. Навіть ваш субоптимальний пробний розділ не впливає на загальну складність часу - він сприяє O ((sqrt (n)) ^ 2) (і оптимальному, O() (sqrt (n)) ^ 1.5) ) у загальний O (n log log n) (це, якщо множини видаляють кожен елемент у часі O (1) , як це дійсно можна можна очікувати від структури даних на основі словника).
додано Автор Will Ness, джерело
загалом, ви повинні використовувати для i в діапазоні (3, int (math.sqrt (n)) + 1, 2): у вашому def is_prime (n): . окрім цього, ви отримали це! :) До речі, ви могли б використовувати метод сита, щоб знайти список основних простих елементів, а не пробний поділ; але це не впливає на загальну складність. Навіть ваш субоптимальний пробний розділ не впливає на загальну складність часу - він сприяє O ((sqrt (n)) ^ 2) (і оптимальному, O() (sqrt (n)) ^ 1.5) ) у загальний O (n log log n) (це, якщо множини видаляють кожен елемент у часі O (1) , як це дійсно можна можна очікувати від структури даних на основі словника).
додано Автор Will Ness, джерело
насправді, тест підтримує вищезгадані дії. Привітання! :)
додано Автор Will Ness, джерело
насправді, тест підтримує вищезгадані дії. Привітання! :)
додано Автор Will Ness, джерело
@rmunn мій вищевказаний тест емпірично підтримує те, що a.difference_update (b) працює в O (len (b)) . Отже, ні, він не виконується в O (N) , де N = len (a) , який необхідний, щоб зробити загальний час квадратичним. Набори добре працюють тут, і остаточний код оператора виконується в O (n log (log n)) , на наборах. Наборів тут не було.
додано Автор Will Ness, джерело
більше 10 редагувань перетворюють ваше питання (і всі відповіді) на спільноту-вікі; тоді виборці не дають жодної репутації.
додано Автор Will Ness, джерело
більше 10 редагувань перетворюють ваше питання (і всі відповіді) на спільноту-вікі; тоді виборці не дають жодної репутації.
додано Автор Will Ness, джерело
більше 10 редагувань перетворюють ваше питання (і всі відповіді) на спільноту-вікі; тоді виборці не дають жодної репутації.
додано Автор Will Ness, джерело
Ласкаво просимо. у всякому разі, чому ваш початковий код був настільки повільним (оскільки ніхто не відповів на це): k = i/2 є винуватцем. Змінивши його на k = int (math.sqrt (i) + 1) , слід зняти час виконання у діапазоні хвилин . І так, як ви, напевно, знаєте зараз, початкове видалення 40 простих чисел і їх кратні було зроблено методом сита Ерса.
додано Автор Will Ness, джерело
ні, у вихідному коді ви починаєте з 40 ситових кроків, але потім зупиняєтеся, і перемикаєтеся на дуже неоптимальний пробний поділ. зміна n/2 на sqrt (n) робить його менш неефективним TD, але все ще не оптимальним - з одного боку, тестування здійснюється в неправильному напрямку; і ви розбиваєтеся на шанси, а не на прості числа. Ваша остання версія - сито Er, з початковим TD до sqrt. BTW ви можете зробити цей перший крок з ситом Er, також? Чи можете ви зробити це без (майже) написання нового коду? :)
додано Автор Will Ness, джерело
Ласкаво просимо. у всякому разі, чому ваш початковий код був настільки повільним (оскільки ніхто не відповів на це): k = i/2 є винуватцем. Змінивши його на k = int (math.sqrt (i) + 1) , слід зняти час виконання у діапазоні хвилин . І так, як ви, напевно, знаєте зараз, початкове видалення 40 простих чисел і їх кратні було зроблено методом сита Ерса.
додано Автор Will Ness, джерело
ні, у вихідному коді ви починаєте з 40 ситових кроків, але потім зупиняєтеся, і перемикаєтеся на дуже неоптимальний пробний поділ. зміна n/2 на sqrt (n) робить його менш неефективним TD, але все ще не оптимальним - з одного боку, тестування здійснюється в неправильному напрямку; і ви розбиваєтеся на шанси, а не на прості числа. Ваша остання версія - сито Er, з початковим TD до sqrt. BTW ви можете зробити цей перший крок з ситом Er, також? Чи можете ви зробити це без (майже) написання нового коду? :)
додано Автор Will Ness, джерело
ні, у вихідному коді ви починаєте з 40 ситових кроків, але потім зупиняєтеся, і перемикаєтеся на дуже неоптимальний пробний поділ. зміна n/2 на sqrt (n) робить його менш неефективним TD, але все ще не оптимальним - з одного боку, тестування здійснюється в неправильному напрямку; і ви розбиваєтеся на шанси, а не на прості числа. Ваша остання версія - сито Er, з початковим TD до sqrt. BTW ви можете зробити цей перший крок з ситом Er, також? Чи можете ви зробити це без (майже) написання нового коду? :)
додано Автор Will Ness, джерело
Питання Проекту Ейлера тут : він запитує суму всіх простих чисел менше 2 мільйонів.
додано Автор rmunn, джерело
Ви запитали, чому ваше рішення займає стільки часу: це тому, що ви написали алгоритм O (N ^ 2). (Див. тут , якщо ви Не знайомі з позначеннями Big O). Метод difference_update() наборів виконується за час O (N), і ви називаєте його O (N) разів, таким чином, загальний час виконання O (N ^ 2). Коли N отримує більше 2 мільйонів, це дуже багато.
додано Автор rmunn, джерело
Ви запитали, чому ваше рішення займає стільки часу: це тому, що ви написали алгоритм O (N ^ 2). (Див. тут , якщо ви Не знайомі з позначеннями Big O). Метод difference_update() наборів виконується за час O (N), і ви називаєте його O (N) разів, таким чином, загальний час виконання O (N ^ 2). Коли N отримує більше 2 мільйонів, це дуже багато.
додано Автор rmunn, джерело
Такі речі ви зустрічаєтеся часто в задачах Проекту Ейлера: вони розроблені для того, щоб зробити O (N ^ 2) алгоритми болісно повільними. З огляду на великі числа, з якими ви маєте справу, ви хочете переконатися, що ваше рішення виконується в найкоротші терміни O (N), або (як ви щойно виявили) може зайняти 7 годин, тоді як рішення іншого користувача займає всього чотири секунди .
додано Автор rmunn, джерело
Не могли б Ви додати посилання на запитання?
додано Автор Ankur Ankan, джерело

10 Відповіді

Питання:

Знайдіть суму всіх простих чисел нижче двох мільйонів.

Це просте сито . Ви повинні прочитати про це, але загальна ідея полягає в переборі кожного номера - якщо значення в індексному номері 0 , то це первинне значення і ви позначите кратність цього числа (оскільки всі ці кратні не може бути першокласним). Ігнорувати, якщо 1 (композитний). Я наведу деякі коментарі, щоб пояснити, що саме робить цей код,

marked = [0] * 2000000     # <- just set up the list
value = 3                  # <- starting at 3 then checking only odds
s = 2                      # <- BUT include 2 since its the only even prime
while value < 2000000:
    if marked[value] == 0: # <- if number at index value is 0 it's prime
        s += value         #    so add value to s (the sum)
        i = value          # <- now mark off future numbers that are multiples of
        while i < 2000000: #    value up until 2mil
            marked[i] = 1  # <- number @ index i is a multiple of value so mark
            i += value     # <- increment value each time (looking for multiples)
    value += 2             # <- only check every odd number
print s

Дві оптимізації для цього коду:

  1. The initial value of i could be set to value*value == value**2
  2. Could easily change this to use a list of length 1 million since we already know no evens are primes

EDIT:

Хоча я сподіваюся, що моя відповідь допоможе пояснити операції сит для майбутніх відвідувачів, якщо ви шукаєте дуже швидку реалізацію сита , зверніться до це питання . Чудовий аналіз продуктивності за notbu і деяких чудових алгоритмів, розміщених Робертом Вільямом Хенксом!

4
додано
Спасибі, я повторно факторингу мій код, і тепер він може показати результат протягом 2 сек, який був ефективним, ніж програма lassevk: D.
додано Автор bkmagnetron, джерело
Чи можете ви перевірити мій код і сказати мені, що його як сито чи ні.
додано Автор bkmagnetron, джерело

Питання:

Знайдіть суму всіх простих чисел нижче двох мільйонів.

Це просте сито . Ви повинні прочитати про це, але загальна ідея полягає в переборі кожного номера - якщо значення в індексному номері 0 , то це первинне значення і ви позначите кратність цього числа (оскільки всі ці кратні не може бути першокласним). Ігнорувати, якщо 1 (композитний). Я наведу деякі коментарі, щоб пояснити, що саме робить цей код,

marked = [0] * 2000000     # <- just set up the list
value = 3                  # <- starting at 3 then checking only odds
s = 2                      # <- BUT include 2 since its the only even prime
while value < 2000000:
    if marked[value] == 0: # <- if number at index value is 0 it's prime
        s += value         #    so add value to s (the sum)
        i = value          # <- now mark off future numbers that are multiples of
        while i < 2000000: #    value up until 2mil
            marked[i] = 1  # <- number @ index i is a multiple of value so mark
            i += value     # <- increment value each time (looking for multiples)
    value += 2             # <- only check every odd number
print s

Дві оптимізації для цього коду:

  1. The initial value of i could be set to value*value == value**2
  2. Could easily change this to use a list of length 1 million since we already know no evens are primes

EDIT:

Хоча я сподіваюся, що моя відповідь допоможе пояснити операції сит для майбутніх відвідувачів, якщо ви шукаєте дуже швидку реалізацію сита , зверніться до це питання . Чудовий аналіз продуктивності за notbu і деяких чудових алгоритмів, розміщених Робертом Вільямом Хенксом!

4
додано
Спасибі, я повторно факторингу мій код, і тепер він може показати результат протягом 2 сек, який був ефективним, ніж програма lassevk: D.
додано Автор bkmagnetron, джерело
Чи можете ви перевірити мій код і сказати мені, що його як сито чи ні.
додано Автор bkmagnetron, джерело

Питання:

Знайдіть суму всіх простих чисел нижче двох мільйонів.

Це просте сито . Ви повинні прочитати про це, але загальна ідея полягає в переборі кожного номера - якщо значення в індексному номері 0 , то це первинне значення і ви позначите кратність цього числа (оскільки всі ці кратні не може бути першокласним). Ігнорувати, якщо 1 (композитний). Я наведу деякі коментарі, щоб пояснити, що саме робить цей код,

marked = [0] * 2000000     # <- just set up the list
value = 3                  # <- starting at 3 then checking only odds
s = 2                      # <- BUT include 2 since its the only even prime
while value < 2000000:
    if marked[value] == 0: # <- if number at index value is 0 it's prime
        s += value         #    so add value to s (the sum)
        i = value          # <- now mark off future numbers that are multiples of
        while i < 2000000: #    value up until 2mil
            marked[i] = 1  # <- number @ index i is a multiple of value so mark
            i += value     # <- increment value each time (looking for multiples)
    value += 2             # <- only check every odd number
print s

Дві оптимізації для цього коду:

  1. The initial value of i could be set to value*value == value**2
  2. Could easily change this to use a list of length 1 million since we already know no evens are primes

EDIT:

Хоча я сподіваюся, що моя відповідь допоможе пояснити операції сит для майбутніх відвідувачів, якщо ви шукаєте дуже швидку реалізацію сита , зверніться до це питання . Чудовий аналіз продуктивності за notbu і деяких чудових алгоритмів, розміщених Робертом Вільямом Хенксом!

4
додано
Спасибі, я повторно факторингу мій код, і тепер він може показати результат протягом 2 сек, який був ефективним, ніж програма lassevk: D.
додано Автор bkmagnetron, джерело
Чи можете ви перевірити мій код і сказати мені, що його як сито чи ні.
додано Автор bkmagnetron, джерело

Кодекс, в основному, використовується за допомогою сита Ератосфена , щоб знайти прості числа, які можуть бути яснішими після вилучення код, який відстежує суму:

marked = [0] * 2000000
value = 3
while value < 2000000:
    if marked[value] == 0:
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2

value ticks up by 2 (since you know that all even numbers above 2 aren't prime, you can just skip over them) and any value that hasn't already been marked by the time you reach it is prime, since you've marked all the multiples of the values below it.

1
додано
Heh, бити мені до це.
додано Автор rmunn, джерело

Кодекс, в основному, використовується за допомогою сита Ератосфена , щоб знайти прості числа, які можуть бути яснішими після вилучення код, який відстежує суму:

marked = [0] * 2000000
value = 3
while value < 2000000:
    if marked[value] == 0:
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2

value ticks up by 2 (since you know that all even numbers above 2 aren't prime, you can just skip over them) and any value that hasn't already been marked by the time you reach it is prime, since you've marked all the multiples of the values below it.

1
додано
Heh, бити мені до це.
додано Автор rmunn, джерело

Кодекс, в основному, використовується за допомогою сита Ератосфена , щоб знайти прості числа, які можуть бути яснішими після вилучення код, який відстежує суму:

marked = [0] * 2000000
value = 3
while value < 2000000:
    if marked[value] == 0:
        i = value
        while i < 2000000:
            marked[i] = 1
            i += value
    value += 2

value ticks up by 2 (since you know that all even numbers above 2 aren't prime, you can just skip over them) and any value that hasn't already been marked by the time you reach it is prime, since you've marked all the multiples of the values below it.

1
додано
Heh, бити мені до це.
додано Автор rmunn, джерело

This code basically sums up all the primes < 2000000 using the Sieve of Eratosthenes concept:

позначено величезний масив, повний нулів.

Кожен раз, коли значення менше 2000000, перевірте, чи позначено значення в масиві. Позначення може розглядатися як позначення позиції масиву як 1. Для, наприклад, якщо ви хочете позначити значення, ви позначаєте позицію цього значення у вашому маркованому масиві як 1 (відпочинок - всі нулі).

Далі, ви встановлюєте i на це значення (i - це значення, яке використовується для циклу while). Хоча i менше 2000000, позначте позначений масив для цього конкретного значення. Потім збільште i на це значення. Це робиться так, щоб: Якщо ви позначите всі кратні 2, вам не потрібно повторювати всі їх у наступній ітерації. Для напр. якщо ви позначите всі кратні 2, наступний крок можна почати з 3 з 3 ^ 2 = 9, оскільки всі менші кратні вже будуть позначені.

Refer Sieve of Eratosthenes and this video for further details.

1
додано

Ця відповідь використовує підхід сита Ерастотена для позначення непростих чисел (це те, що позначено список), а потім переглядаються та додаються лише значення, які не були позначені. Дивіться статтю Вікіпедії для більш докладної інформації.

0
додано
Ей перевірте мій код і скажіть мені, що це як сито Ерастотена чи ні.
додано Автор bkmagnetron, джерело

Ця відповідь використовує підхід сита Ерастотена для позначення непростих чисел (це те, що позначено список), а потім переглядаються та додаються лише значення, які не були позначені. Дивіться статтю Вікіпедії для більш докладної інформації.

0
додано
Ей перевірте мій код і скажіть мені, що це як сито Ерастотена чи ні.
додано Автор bkmagnetron, джерело

Ця відповідь використовує підхід сита Ерастотена для позначення непростих чисел (це те, що позначено список), а потім переглядаються та додаються лише значення, які не були позначені. Дивіться статтю Вікіпедії для більш докладної інформації.

0
додано
Ей перевірте мій код і скажіть мені, що це як сито Ерастотена чи ні.
додано Автор bkmagnetron, джерело
ІТ КПІ - Python
ІТ КПІ - Python
625 учасників

Канал обговорень про всякі штуки зі світу пайтону. Прохання: 0. мати повагу одне до одного; 1. не матюкатися в сторону людей; 2. не захламляти тред повідомленнями по одному слову;