[Java/알고리즘] 1부터 100까지의 소수의 합을 구하자!
(에라토스테네스의 체)
1부터 100까지의 소수의 합을 구하기 위해서는
우선 소수에 대해서 알아야 합니다.
소수는 1과 자기자신만으로
나누어지는 수를 소수라고 합니다.
예를들어 17은 1과 17만으로 나누어집니다.
하지만 15는 1,3,5,15 로 나누어 지죠
그럼 17은 소수라고 할 수 있습니다.
아래는 그냥 에라토스테네스의 체를 사용하지 않은 소수 구하기 입니다.
public class Prime {
public static void main(String args[]){
// 합을 구하기 위한 변수
int sum = 0;
// 1은 제외해야 하기 때문에 2부터 시작
for(int num=2; num<=100; num++){
// 1과 자기 자신만으로 나누어지는 값을 소수라고 함
// 1과 자기 자신을 체크하기 위한 변수
int count = 0;
for(int i=1; i<=num; i++) {
if(num%i == 0) {
count++;
}
}
if(count == 2) {
sum += num;
// 소수 출력
System.out.print(num+",");
}
}
// 소수의 합 출력
System.out.println(sum);
}
}
또 다른 소수를 찾는 방법으로는
에라토스테네스의 체라는 알고리즘을 이용하여 찾는 것 입니다.
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다.
아래는 에라토스테네스의 체를 활용하여 소수의 합을 구하는 방법입니다.
public class Eratos {
public static void main(String[] args) {
// ArrayList로 구현
ArrayList<Boolean> primeList;
int n = 100;
// n+1만큼 할당
primeList = new ArrayList<Boolean>(n+1);
// 0번째와 1번째를 소수 아님으로 처리
primeList.add(false);
primeList.add(false);
// 2~ n 까지 소수로 설정
for(int i=2; i<=n; i++ )
primeList.add(i, true);
// 2 부터 ~ i*i <= n
// 각각의 배수들을 지워간다.
for(int i=2; (i*i)<=n; i++){
if(primeList.get(i)){
for(int j = i*i; j<=n; j+=i) {
primeList.set(j, false);
}
}
}
StringBuffer sb = new StringBuffer();
int sum = 0;
for(int i=0; i<=n; i++){
if(primeList.get(i) == true){
sum += i;
sb.append(i);
sb.append(",");
}
}
System.out.println(sb.toString());
System.out.println(sum);
}
}
알고리즘 원리를 보시죠
결과
1부터 100까지의 소수의 합을 구하자! (에라토스테네스의 체)
포스팅을 마치겠습니다.
도움이 되었다면 공감과 +a 감사합니다!
