Python: Алгоритм простого числа с квадратом root

Question

Я пытаюсь решить эту проблему, и, несмотря на то, что я обнимаю ее, я зацикливаюсь снова и снова.

У меня есть список, составленный из одного элемента [2] и с учетом этого и зная, что для получения простого числа $ N $ я должен проверить, что у него нет простого множителя, меньшего или равного $ \ sqrt {N} $, сгенерируйте все простые числа от 3 до 100

Мой код следующий, и я постараюсь объяснить, как я его создал:

prime_numbers = [2]

for k in range(3,100):  # k runs on all numbers to check them
    for i in range (0,len(prime_numbers)): # i is the index of the elements in my list
        if prime_numbers[i] <= sqrt(k):    # first I need to check the sqrt condition
            if k % prime_numbers[i] ==0:     # check that element in list divides k
                k+=1                         # if so k++ and break the cicle
                break
            else:
                i +=1                        # otherwise go to the next elem of the list
        else:                              #if the sqrt condition is not met I have found a prime number    
            value = k
        prime_numbers.append(value)

Когда я запустить этот код он попадает в al oop без выхода, и я не могу определить, где проблема. Мое лучшее предположение было бы исправить самое отступное условие, но все попытки, которые я сделал, привели к провалу. Спасибо всем, кто готов принять участие.

Answer 1

Это работает:

prime_numbers = [2]

for prime_candidate in range(3, 100):
    for known_prime in prime_numbers:
        if known_prime <= sqrt(prime_candidate):
            if prime_candidate % known_prime == 0:
                break
    else:
       prime_numbers.append(prime_candidate)

Ваша проблема в основном заключалась в том, что i += 1 не препятствует добавлению prime_numbers.append.

Символ for / else может быть заменен отдельным флаг для запуска всех случаев, когда break не происходило раньше.

Answer 2

Спасибо всем, кто предложил решение. Тем временем я сам придумал один.

prime_numbers = [2]


for k in range(3,100):
    for i in range (0,len(prime_numbers)):
        if prime_numbers[i] <= sqrt(k):
            if k % prime_numbers[i] ==0:
                k+=1
                break
            else:
                i +=1
        else:
            value = k
    if(value > max(prime_numbers)):
        prime_numbers.append(value)

Answer 3

Один из способов получить это:

from math import sqrt

prime_numbers=[2]

for k in range(3,101):
    prime=True
    for i in range(2, int(sqrt(k))+2):
        if k%i == 0:
            prime=False
            break
    if prime:
            prime_numbers.append(k)

print(prime_numbers)

#Output:
#[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Примечания:

• Это range(3,101), а не range(3,100), если предполагается, что вы хотите отметьте все числа , включая 100, в противном случае ваш последний проверенный номер будет 99.
• Иметь логическую переменную prime; начнем с предположения, что число простое (prime=True)
• sqrt(k) возвращает число с плавающей запятой, в то время как ваш диапазон ожидает целые числа; как таковой - int(sqrt(k)). Это +2, чтобы гарантировать, что ваш диапазон значений «до» никогда не будет меньше значения «из» 2.
• if k%i == 0 (если у вас есть делитель), число не простое (prime=False) и break for l oop, чтобы перейти к следующему k
• Это может быть моим "pythoni c", когда вы понимаете список, но вам может быть легче понять в текущий формат