반응형
안녕들 하시죠!
이번시간에는 기초 알고리즘 단골 문제인 입력받은 숫자 n까지의 소수갯수 구하기를 Java언어로 풀어보겠습니다.
문제
1부터 입력받은 숫자 n까지의 소수의 갯수를 구해라.
풀이
입력받은 숫자까지의 모든 숫자를 나누기 연산을 통해 비교한다.
입력받은 n이 5라면, 2부터 시작해서 일일이 나누어본다.
2%2 , 3%2, 3%3, 4%2, 4%3, 4%4, 5%2, 5%3 ...
|
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
27
28
29
30
|
import java.util.Scanner;
public class Test1 {
public static int getCount(int n) { // 입력받은 숫자까지의 소수를 계산하는 메소드
int total = 0;
int num = 2;
while (num <= n) {
for (int i = 2; i <= num; i++) {
if (num % i == 0 && i != num) { // 입력받은 숫자 이외에 다른 숫자로 나누어 떨어질 경우 ( 소수가 아님 ) break
break;
}
if (num % i ==0 && i == num) { // for문의 i가 증가해 본인과 같아져 나누어 떨어질 경우 ( 소수 )
total++; // 소수의 갯수를 count하는 total 증가
}
}
num++;
}
return total;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int result = getCount(n);
System.out.println(result);
}
}
|
cs |
문제점
숫자가 커지면 커질수록 일일이 비교하는 것은 효율성이 떨어집니다.
100000 정도의 숫자만 입력해도 계산시간이 꽤나 걸립니다.
아래에서 시간복잡도를 통한 비교를 해보겠습니다.
시간복잡도
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public static void main(String[] args) {
long start = System.currentTimeMillis();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int result = getCount(n);
System.out.println(result);
long end = System.currentTimeMillis();
System.out.println("수행시간 : " + (end - start)/1000.0);
}
|
cs |
에라토스테네스의 체 알고리즘
고대 그리스 수학자 에라토스테네스가 발견한 제곱근을 이용한 소수를 구하는 방법.
소수를 구하는 최적의 알고리즘이라고 합니다.
소수는 n의 배수가 아니고 입력받은 수를 그 수보다 작은 수들로 나누어서 떨어지면 소수가 아니다.
그러므로, 모두 나누어 볼 필요없이 n 제곱근 까지만 나누어서 떨어지면 소수가 아니다.
|
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.Scanner;
public class Test1 {
public static int getCount(int n) { // 입력받은 숫자까지의 소수를 계산하는 메소드
int[] arr = new int[n + 1];
int c = 0;
for (int i = 2; i <= n; i++) { // 입력받은 숫자까지의 모든 숫자들을 배열에 초기화한다.
arr[i] = i;
}
int Sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= Sqrt; i++) { // 제곱근 까지만 계산
if (arr[i] == 0) { // 0으로 초기화 되어있는 숫자들은 건너뛴다.
continue;
}
for (int j = i + i; j <= n; j += i) { // 현재 숫자(i)를 제외한 제곱수들은 모두 0으로 초기화.
arr[j] = 0; // 0이 들어있는 번지는 소수가 아니다.
}
}
for (int i = 2; i <= n; i++) {
if (arr[i] != 0) {
c++;
}
}
return c;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int result = getCount(n);
System.out.println("개수 : " + result);
long end = System.currentTimeMillis();
System.out.println("수행시간 : " + (end - start) / 1000.0);
}
}
|
cs |
수행시간
오늘은 여기까지입니다 감사합니다.
'알고리즘' 카테고리의 다른 글
| Java 원형큐 구현 (0) | 2019.06.23 |
|---|---|
| Java 링크드리스트 구현 (0) | 2019.06.22 |
| 백준 10828번 (스택) (0) | 2019.05.10 |
| 백준 2750번 (버블정렬) (0) | 2019.05.01 |
| 백준 1000번 (0) | 2019.04.16 |
