[python] 소수 찾기

문제

수열 A에 있는 수들을 합한 값을 구하기로 한다. 하지만 단순히 모든 값을 다 더하는 것은 이젠 진부하다. 그래서 수열의 앞에서 소수 번째에 위치한 값들을 모두 더하려고 한다. 수열의 값들이 주어졌을 때, 계산된 수의 합을 구해보자.

 

 

입력

첫째 줄에 수열 A의 길이 N이 주어진다.

둘째 줄에는 A1, ... , An 이 공백을 두고 주어진다. Ai는 A의 i번째에 위치한 값을 의미한다.

 

• 1 ≤ N ≤ 100,000
• -100 ≤ Ai ≤ 100
• 입력에서 주어지는 모든 수는 정수이다.

 

 

제곱근을 이용한 방법

import sys
input = sys.stdin.readline

n = int(input())
numList = list(map(int, input().split()))

result = 0

for i in range(2, n+1):
	prime = True
	j = 2
	while j*j <= i:
		if i % j == 0:
			prime = False
			break
		j += 1
	
	if prime:
		result += numList[i-1]

print(result)

 

 

 

에라토스테네스의 체를 이용한 방법

이 방법이 해당 문제에서 효율이 더 좋게 나온다.

def findPrime(n):
	
	is_prime = [num for num in range(n+1)]
	prime = []
	
	for i in range(2, n+1):
		
		if is_prime[i] == 0:
			continue
		prime.append(i)
		
		for j in range(2*i, n+1, i):
			is_prime[j] = 0
			
	return prime

import sys
input = sys.stdin.readline

n = int(input())
numList = [0] + list(map(int, input().split()))

result = 0

primes = findPrime(n)

for i in primes:
	result += numList[i]

print(result)

 

 

 

※출처

https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반