처음 n 소수를 계산하는 방법은 무엇입니까?

Question

is_prime 기능을 사용할 수 있다고 가정합니다. 변수 n이 양의 정수와 관련 있다고 가정합니다. 첫 번째 n 소수의 합계를 계산하는 데 필요한 명령문을 작성하십시오. 합계는 변수 total과 연관되어야합니다.

참고 : is_prime은 정수를 매개 변수로 취하고 해당 정수가 소수 인 경우에만 True을 반환합니다. 글쎄, 난 이런 is_prime 기능 썼다 :

def is_prime(n): 
    n = abs(n) 
    i = 2 
    while i < n: 
     if n % i == 0: 
      return False 
     i += 1 
    return True 

을하지만 N == 0을 제외하고 작동합니다. 모든 정수에 대해 작동하도록 수정하려면 어떻게해야합니까? 첫 번째 n 소수의 합계를 구하는 함수 작성 방법과 양수가 아닌 모든 가능한 입력에 대해 작동해야하는 is_prime 함수 수정 방법에 대한 해답을 찾고자합니다.

Answer 1

i = 0 또는 1에 대한 대답을 하드 코딩하지 않는 이유는 무엇입니까?

n = abs(n) 
i = 2 
if(n == 0 || n == 1) 
    return true //Or whatever you feel 0 or 1 should return. 
while i < n: 
    if n % i == 0: 
     return False 
    i += 1 
return True 

그리고 일부 숫자를 생략하면 알고리즘 속도를 향상시킬 수 있습니다. 이 스크립트는 n의 제곱근까지만 확인합니다. 숫자에 하나 이상의 요소가있는 경우 복합 숫자에 제곱근 인보다 큰 요소가 없으므로 하나의 숫자는 해당 숫자의 제곱근보다 먼저 발생합니다. 많은 수를 테스트 할 때 이것은 큰 차이를 만듭니다.

n = abs(n) 
i = 2 
if(n == 0 || n == 1) 
    return true //Or whatever you feel 0 or 1 should return. 
while i <= sqrt(n): 
    if n % i == 0: 
     return False 
    i += 1 
return True 

Answer 2

글쎄, n이 0 또는 1 일 때 어떻게됩니까?

당신이

i = 2 
while i < n: #is 2 less than 0 (or 1?) 
    ... 
return True 

는 0 또는 1의 n은 False가, 다음이 당신이 당신의 조건부 (또는 자체 기능)이 경우 설명하기 위해 수정할 필요가 있음을 제안하지 않는 반환하려면?

Answer 3

문제 설명에 n은 양의 정수입니다. 따라서 assert(n>0)과 프로그램 outer-loop가 결코 음수 값이나 0이 아닌 is_prime()이되지 않도록하십시오.

알고리즘 - 모든 연속 홀수 수의 시험 구분합니다 ('홀수'는 당신을위한 주요 속도 향상 것) - 작품,하지만 매우 느리게 될 것입니다. 영감을 얻으려면 prime sieve을보십시오.

Answer 4

이 시도 : 다음과 같이

if(n==0) 
    return true 
else 
    n = abs(n) 
    i = 2 
    while i < n: 
     if n % i == 0: 
      return False 
     i += 1 
    return True 

Answer 5

과제입니다.

is_prime 함수가 있다고 가정하십시오. 변수 n이 양의 정수와 관련 있다고 가정합니다. 첫 번째 n 소수의 합계를 계산하는 데 필요한 명령문을 작성하십시오. 합계는 변수 total과 연관되어야합니다.

NVRAM 바르게 코멘트에 지적 (그리고 아무도에 집어 것으로 나타납니다)으로

, 질문 상태는 "함수 is_prime의 가용성을 가정합니다."

에 해당 기능을 쓰려면이 있어야합니다. 당신은 을 수행해야합니까해야 "첫 n 소수의 합계를 계산하는 데 필요한 문을 작성"입니다. 그것에 대해

의사 코드는 것 같은 뭔가 :

primes_left = n 
curr_num = 2 
curr_sum = 0 
while primes_left > 0: 
    if is_prime(curr_num): 
     curr_sum = curr_sum + curr_num 
     primes_left = primes_left - 1 
    curr_num = curr_num + 1 
print "Sum of first " + n + " primes is " + curr_sum 

난 당신이 그것을 찾을 수 있습니다 생각, 당신은 단지 선택의 여지가 귀하의 언어로 그 의사를 구현하는 경우, 즉 당신이해야 할 모든 수 있습니다.

할당을 테스트하기 위해 is_prime의 구현을 찾고 있다면 어쨌든 몇 가지 작은 값만 테스트 할 것이기 때문에 얼마나 효율적인지는 중요하지 않습니다. 또한 사용할 코드의 제약 조건을 고려할 때 2보다 작은 숫자에 대해서도 걱정할 필요가 없습니다. 이런 식으로 뭔가가 완벽하게 허용 :

이

def is_prime(num): 
    if num < 2: 
     return false 
    if num == 2: 
     return true 
    divisor = 2 
    while divisor * divisor <= num: 
     if num % divisor == 0: 
      return false 
     divisor = divisor + 1 
    return true