https://www.acmicpc.net/problem/16400코드n = int(input())def prime_number(n): is_prime = [True]*(n+1) is_prime[0] = False is_prime[1] = False prime = [] for i in range(2, n+1): if is_prime[i]: for j in range(i*2, n+1, i): is_prime[j] = False prime.append(i) return primeprime = prime_number(n)dp = [0]*(n+1)dp[0] = 1for p in prime: for..
소수판별
https://school.programmers.co.kr/learn/courses/30/lessons/92335정답 코드function isPrime(num) { if (!num || num === 1) return false; for (let i = 2; i 문제 풀이 과정1. 에라토스테네스의 체 이용문제 풀이 과정소수를 판별하기 위한 알고리즘인 "에라토스테네스의 체"를 이용하여 문제를 풀이하려 했다. - 소수인지 판별하기 위한 함수 `prime`1. 에라토스테네스의 체로 어떤 수가 소수인지 미리 구해놓는다.2. 인자로 받은 수가 소수인지 판별하는 함수 `isPrime`을 리턴한다.- `solution` 동작 과정1. n을 k진수로 변환2. '0'으로 splilt3. split의 결과로 생성된 ..
6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 코드 #include #include const int MAX = 1000001; int is_prime[1000001]; void prime(int n){ is_prime[0] = 1; is_prime[1] = 1; for(int i=2;i
11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 코드 # 에라토스테네스의 체 def primeNum(n): num_arr = [False] * (n+1) res = [] for i in range(2, n+1): if num_arr[i]: # 이미 지워진 수라면 continue if n % i == 0: res.append(i) for j in range(i * 2, n + 1, ..
