1. 풀이 처음엔 에라토스테네스의 체를 이용하여 소수를 모두 구하고, dfs를 이용하여 구하려고 했다. (소스코드1) (1)소수리스트가 정렬되어 있기 때문에 크기가 N보다 커지면 벡트래킹. (2) i번째 숫자를 추가했을때 x값이 나오는 경우는 더이상 탐색하지 않기위해서 visited[i][x]를 관리해 주었지만 시간초과가 났다. ​ 정답은 골드바흐의 추측을 응용해서 풀이하는것이였다. (소스코드2) [골드바흐의 추측] 2보다 큰 모든 짝수는 2개의 소수의 합으로 표현할 수 있다. 이를 응용하면 가장 작은 네개의 소수로 만들 수 있는 수 8(2+2+2+2)이상의 숫자는 소수4개로 표현할 수 있다는 뜻인데 그 방법은 다음과 같다. ​ (1) N이 짝수일때 N이 짝수일때는 N-4도 짝수이다. (N-4>=4) 따..

0~size-1까지의 모든 숫자들에 대해서 소수인지를 판별 1. isNotPrime는 소수인것이 0 int isNotPrime[size]; void eratosthenes(size) { isNotPrime[1] = 0; isNotPrime[1] = 1; // 0과 1은 소수가 아니다. for (int i = 2; i*i < size; i++) { if (!isNotPrime[i]) { //소수이거나, 아직 탐색을 안했다면 (isNotprime은) 0 for (int j = i * i; j < size; j += i) { isNotPrime[j] = 1; } } } } 2. isPrime는 소수인것이 1 #에라토스테네스 isPrime=[1 for i in range(size)] def prime(): is..

소수구하기 수행시간(1,679 ms) 수행시간(6,004 ms이상) L=[2] for i in range(3,1000001,2): isDecimal=True for j in L: if i%j==0: isDecimal=False break if isDecimal==True: L.append(i) print(*L) 소수가 아닌수 a는 a보다 작은 소수에 의해 나누어 떨어짐 def isDecimal1(a): import math if a==2: return True if a==1 or a%2==0: return False for i in range(3,int(math.sqrt(a))+1,2): if a%i==0: return False return True L=[] for i in range(1000000):..

1. 풀이 (1) 에라토스테네스의 체를 이용하여 모든 소수를 찾고 (2) 투포인터를 이용하여 합이 N이되는 경우의 수를 찾으면 된다. ​ * 투포인터 : 시작부분s와 끝부분e, [s,e)까지의 합 S라 할때, (시간복잡도는 O(n)) (이때 L의 각 원소는 양수이고, N도 양수여야 한다) i) S==N이면 cnt+=1, e+=1(e가 범위밖(==size+1)이면 끝내기), S+=L[e-1] ii) SN이면 S-=L[s], s+=1 ​ 2. 소스코드 N=int(input()) isPrime=[1 for i in range(N+1)] isPrime[0]=isPrime[1]=0 primeL=[] def aratos(): for i in range(2,N+1): if isPrime[i]: primeL.appen..