자바 소수 구하기 (for문,if문 사용)

안녕하세요!~

오늘은 자바를 시작할 때, 아마 한 번쯤은

해봤을 자바 소수 구하기를 해보겠습니다.

public class minority {
	public static void main(String[] args) {
		// 소수의 정의 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 정수
		int minority = 0; // 소수 
		int count=0; // 시도 횟수
		// 소수는 0,1 은 해당되지 않으므로 2부터 시작
		for(int i=2; i<=100; i++) {
			for(int j=2; j<=i; j++) {
				count++;
				if(i%j==0) {
					minority++;
				}
			}
			// 소수를 찾을때마다 실행 (범위 100까지)
			if(minority==1) 
			{
				System.out.println("소수: "+ i + " 시도한 횟수: "+ count);
			}
		minority=0;
		}
	}
}

2~100까지의 소수를 구하는데

연산 횟수는 대략 5,000번...

여기서 생각을 해볼 수 있는 거는 이미 소수가 아님을

알았는데 계속해서 연산을 하는 경우가 있습니다.

그래서 이번에는 break;를 사용해서

연산 횟수를 줄여보겠습니다.

public class dd {
	public static void main(String[] args) {
		int count = 1; // 소수를 구하기 위한 연산 횟수
		
		// 0,1은 제외 2부터 시작
		for(int i=2; i<=100; i++) {
			int j;
			for(j =2; j<i; j++) {
				count++;
				// 자기 자신을 제외 나누어 떨어지면 소수가 아님
				// 굳이 추가 연산을 할 필요가 없으므로 break;
				if(i % j == 0) 
					break;
				}
				// 자기 자신을 제외하고 나누어 떨어지는 수가
				// 없었을시에는 해당 숫자를 출력
				if(i == j)
					System.out.println("소수: " + i + " 시도 횟수: " + count);
		}
	}
}

첫 번째 방법과 거의

4배 정도 차이가 보입니다.

현재는 100까지의 범위를 두고

소수를 구하고 있는데 이게 10,000이

된다고 생각하면 더 큰 차이를

보이게 되겠죠.

 

이렇게 오늘은 간단하게

자바 소수 구하는 방법을

알아보았습니다.