python2 prime number(소수) 구하는 알고리즘

소수 : 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수
두 가지 방법이 있다.


첫 번째, 2부터 특정 양의 정수 n까지로 n을 나누었을 때 약수가 자기 자신 n만 있는 경우이다. 예를 들어, 7을 2,3,4,5,6,7로 순서대로 나누어 본다. 그리고 자기 자신 7 이외에 약수가 존재 하지 않는다면 7은 소수가 된다.

#-*- coding: utf-8 -*-

i = input("숫자") # 숫자를 입력 받아서 i에 할당
j = 2

while(True): # 2부터 시작해서 i를 j로 나누어서 나머지가 0이 될 때까지 j를 계속 증가
    if(i%j ==0):
        break
    j +=1

if (i==j): # i와 j가 같을 때 즉 j가 i 자기 자신과 같으면 소수다.
    print i,j
    print i,"는 소수임"
else:
    print i,j
    print i,"는 소수아님"

숫자7
7 7
7 는 소수임


두 번째, 첫 번째 방법처럼 2부터 굳이 자기 자신까지 나누어 볼 필요 없다. 2부터 특정 양의 정수 n의 제곱근 까지로 n을 나누었을 때 약수가 존재 한다면, n은 소수가 아니다. 예를 들어, 양의 정수 25가 소수인지 확인하기 위해서는, 2부터 25의 제곱근인 5인 (2,3,4,5)로 25를 나누었을 때 약수가 존재 한다면 25는 소수가 아니다.

 #-*- coding: utf-8 -*-
import math

i = input("숫자") # 숫자를 입력받아서 i에 할당
j = 2

while(True):
    if(j<= math.sqrt(i)): # i가 25일 때, 2,3,4,5 까지 나누어봄
        if(i%j==0):
            print i,j
            print i,"는 소수아님"
            break
        else:
            j = j+1

    else: # 6~ 25 인 경우
        print i,j
        print i,"는 소수임"
        break




첫 번째 방법을 이용하여, 숫자를 입력 받아 2부터 입력받은 숫자까지의 소수의 합을 구해보기

#-*- coding: utf-8 -*-

i = input("숫자")
j=2
sum=0
for j in range(2,i+1):
    k=2
    while(True):
        if(j%k==0):
            break;
        k+=1
    if(j==k):
        sum+=j
        
print sum

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째