알고리즘 소수 구하기

소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

 

코테에서 소수 구할 때 딱 2가지로 풀면 된다.만약, 1부터 n까지 자연수 중에 소수를 다 더하라는 문제가 있다.

 

1. 2중 for문 / 처음 for문은 2부터 시작(1은 소수가 아니라서 미리 제외) / 서브 for문은 i의 제곱근까지만 나눠주면 된다(효율성)

public class 소수찾기 {
	public int solution(int n) {
   		int sum=0;
		for (int i = 2; i <= n; i++) {// 1은 소수가 아니라서 2부터 시작
			boolean flag = false;
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i % j == 0) { // 나누어떨어지면 소수X
					flag = true; // falg를 false로 바꿔서 소수가 아니라고 체크
					break; // break를 안 해주면 효율성 테스트 통과 못함
				}
			}
			if (flag == false) // 소수인 숫자는 flag가 변하지 않고 true
				sum+=i;
		}
		return sum;
	}
}

 

1. 1차 for문 : 2부터 n까지(n포함)
2. flag를 false로 두고 소수가 아닐 때 flag를 true로 바꿔줄 것이다.
3. 2차 for문 : 2부터 i의 제곱근까지를 나눠준다.(i의 제곱근 포함)
4. i를 j로 나눴을 때 0이라면(=소수라면) flag를 true로 바꿈 -> 그리고 break(break를 해서 아닌건 빨리 탈출하게 해준다)
5. 만약 flag가 false일 경우에만 소수인 i의 수를 모두 더해라.

 

 

2. 1이랑 똑같은데 2차 for문에서 범위 설정을 i까지 하면 된다.(i는 포함x)

public class 소수찾기2 {
	public int solution(int n) {
   		int sum=0;
		for (int i = 2; i <= n; i++) {// 1은 소수가 아니라서 2부터 시작
			boolean flag = false;
			for (int j = 2; j < i; j++) {
				if (i % j == 0) { // 나누어떨어지면 소수X
					flag = true; // falg를 false로 바꿔서 소수가 아니라고 체크
					break; // break를 안 해주면 효율성 테스트 통과 못함
				}
			}
			if (flag == false) // 소수인 숫자는 flag가 변하지 않고 true
				sum+=i;
		}
		return sum;
	}
}