특정 세트에서 모든 소수를 얻으려면 어떻게해야합니까?

Question

def all_primes(start,end): 
    list_nonprimes = [] 
    list_primes = [] 

    for i in range(start,end): 
     for a in range(2,i): 
      if i % a == 1 and i not in list_nonprimes: 
       if i not in list_primes: 
        list_primes.append(i) 
      else: 
       list_nonprimes.append(i) 

    return list_primes 

왜 출력이 잘못 되었습니까?

>>> all_primes(1,10) 
[3,5,7,9] 

9를 어떻게 제거합니까?

Answer 1

덜 현재 확인하고있는 수보다,이 작업을 수행하는 더 간단한 방법이있다 :

이

def all_primes(start,end): 
    list_primes = [] 

    for i in range(2,end): 
     for a in list_primes: 
      if i % a == 0: 
       break 
     else: 
      list_primes.append(i) 

    return [x for x in list_primes if x >= start] 

이를 이해하는 열쇠가 알고있다 방법 for...else 파이썬에서 작동합니다. 본질적으로 for 루프는 else 문을 가질 수 있으며 루프 평가 중에 break 문을 실행하지 않은 경우에만 실행됩니다.

Answer 2

변화는 그것에서 :

 if i % a == 1 and i not in list_nonprimes: 
      if i not in list_primes: 
       list_primes.append(i) 
     else: 
      list_nonprimes.append(i) 

에 : 제외

 if i % a == 0 and i not in list_primes: 
      if i not in list_nonprimes: 
       list_nonprimes.append(i) 
     else: 
      list_primes.append(i) 

: 당신은 대신 Sieve of Eratosthenes을 구현 고려할 수 있습니다. 이해하기 쉽고 훨씬 효율적입니다. 이미 본질적으로 소수의 목록을 생성하고 이후

Answer 3

내가 잘못 가고있는 곳을보기 위해 코드를 살펴 보았지만 꽤 많이 변경되고 최적화되었습니다. 나는 코드를 주석 처리 했으므로 희망적으로 설명된다.

def all_primes(start,end): 
    list_nonprimes = [] 
    list_primes = [] 

    for i in range(start,end): 
     # if already present in non_primes, skip 
     if i in list_nonprimes: continue 

     # if already present in primes, skip 
     if i in list_primes: continue 

     # if 2, mark it as prime. Special case 
     if i == 2 : 
      list_primes.append(i) 
      continue 

     # even numbers are not prime 
     if i%2 == 0: 
      list_nonprimes.append(i) 
      continue 

     # only check divisibility with odd numbers starting at 3 
     # and ending at sqrt(i) 
     for a in range(3,int(i**0,5)+1,2): 
      if i % a == 0 : 
       list_nonprimes.append(i) 
       break 

     # if we got here, and the number wasn;t added to non_primes 
     # it must be a prime 
     if i not in list_nonprimes: list_primes.append(i)    

    return list_primes 

start = 2 
end = 10 
print all_primes(start, end) 

Demo