숫자가 소수인지 여부 확인

Question

여러 번 논의 된 적이 있습니다. 나는 그것을 읽었다. 그러나 어떻게 든 나는 그것을 얻을 수 없다. 입력 한 숫자가 소수인지 아닌지를 결정하는 프로그램을 작성하고 싶습니다. 구현의

하나는 내가 인터넷에서 어딘가에서 발견

from math import * 

def main(): 
    n = abs(input("Enter a number: ")) 
    i = 2 
    msg = 'is a prime number.' 
    while i <= sqrt(n): 
     if n % i == 0: 
      msg = 'is not a prime number.' 
     i = i + 1 
    print n, msg 


main() 

여기에 몇 가지 질문 : 위에서

• , i이며, 무엇은 시작 값이 않는 이유 2?
• i = i + 1는이 프로그램에서 무엇을합니까?
• 'is a prime number.'이 본문 루프 밖에 있더라도 인터프리터는 어떻게 인쇄해야하는지 어떻게 알 수 있습니까?

Answer 1

소수는 1과 그 자체로 나눌 수있는 숫자입니다. 사용하는 방법은 후보 번호 n을 2에서 다른 모든 번호로 나눠서 시도하는 것입니다. 그러나 숫자 i이 숫자 n의 제수이면 n/i이고 그 중 하나 이상이 sqrt(n)보다 작거나 같아야하므로 sqrt(n)까지만 테스트하면됩니다. 실제적으로 우리는 소수를 실제로 테스트 할 필요가 있습니다. 그러나 우리는 소수의리스트를 가지고 있지 않기 때문에 모든 것을 테스트 할 것입니다.

무엇이 위의 i입니까? 왜 2 개의 시작 값을 얻었습니까?

i은 n의 잠재적 인 요소입니다. 우리는 1이 n을 나눌 지 신경 쓰지 않기 때문에 2로 시작합니다. (그리고 쉽게 알 수 있습니다) 왜냐하면 프라임 정의가 허용/기대하기 때문입니다.

이 구체적인 예에서 i = i + 1 문은 무엇입니까? 프로그램에서 그 사용법을 볼 수 없습니다.

while i <= sqrt(n)으로 정의 된 루프의 끝에서 i 값이 증가합니다. n의 다음 후보 약수를 테스트하기 위해 i을 사전에 보내는 것을 의미합니다.

마지막으로 파이썬은 '언제든 소수를 인쇄합니다.' 그것은 몸 루프에서 벗어나지 만?

"은 소수"로 초기화하고 어떤 제수라도 찾으면 루프 내에서 "소수가 아닙니다"로 바꿉니다. 루프가 제수를 찾지 못하거나 루프가 실행되지 않으면 우리가 설정 한 초기 값인 "소수입니다"를 사용합니다. 부수적으로 당신은 제수를 발견 할 때 루프 밖으로 break 수 있습니다; 그 후 시험을 치르는 것은 아무런 의미가 없습니다.

while에서 사용할 변수에 비해 sqrt(n)을 while 및 store 외부에서 계산하려는 경우가 많습니다. 비교적 반복적 인 반복마다 제곱근을 다시 계산할 수 있습니다.

Answer 2

나는 각 행이 무엇을 설명하기 위해 측면에 의견을 추가했습니다 : (n의 제곱근까지)

from math import * # imports everything from the math module 

def main(): 
    n = abs(input("Enter a number: ")) # gets input from the user 
    i = 2 # starts off at 2 because all input is divisble by 1 
    msg = 'is a prime number.' # the message is initially set 
    while i <= sqrt(n): 
     if n % i == 0: # if 'i' divides evenly into n 
      msg = 'is not a prime number.' # only set if it isn't a prime 
     i = i + 1 # increases 'i' by 1 so it can check every value up to the square-root of 'n' (to see if it divides evenly) 
    print n, msg 


main() 

이 프로그램은 i의 모든 값을 통과하는 모든 가능한 있도록 인자가 확인됩니다.

이 거친 프라임 검사의 종류 및 주요하지 않은 많은 비효율적이다 : 그것은 그 숫자의 제곱근에 모든 숫자까지 반복되며, 입력이 숫자 1234567890 같았다 경우 , 35147 (반올림 됨)입니다. return 문을 사용하면 루프가 끊어 지므로 첫 번째 숫자 인 2을 확인하면 2으로 균등하게 나눌 수 있기 때문에 소수가 아닌 것으로 선언됩니다. return을 사용하면 기능을 중지하고 35,146 개의 계산을 절약 할 수 있습니다. 이는 엄청난 숫자는 아니지만 (적어도 컴퓨터의 경우) 여전히 메모리 효율성이 높으며 시간이 덜 소요됩니다.

def isPrime(n): 
    '''Checks if 'n' is prime.''' 
    from math import sqrt 
    if n == 0 or n == 1: 
     return False 
    else: 
     for check in range(2, int(sqrt(n))+1): 
      if n % check == 0: return False 
    return True