<Algorithm> 197. 소수구하기(BJO)
by BFine반응형
1. 1929번 소수구하기(BJO)
사용 알고리즘 : 에라토스체네스의 체
-
예전에 공부했던 알고리즘인데 기억할겸 다시 풀어보았다. 전에 공부하고 구현한 건 O(N^2)인데 이번엔 O(Nlog log N)으로 풀었다.
https://www.weeklyps.com/entry/에라토스테네스의-체-소수-구하기 이곳을 참조하여 풀었다.
에라토스테네스 체는 간단하게 2 부터 시작해서 자기 자신을 제외한 배수들을 지워나가는 방법이다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); boolean[] visited = new boolean[b+1]; visited[1] = true; for(long i = 2; i <= b; i++) { if(!visited[(int) i]) { for(long j = i*i; j <= b; j+=i) { visited[(int) j] = true; } } } for(int i = a; i <= b; i++) { if(!visited[i]) { System.out.println(i); } } } } | cs |
반응형
블로그의 정보
57개월 BackEnd
BFine