소수

소수 구하는 알고리즘 1

public class Sosu {

	public static void main(String[] args) {
		
		for(int num=2; num <= 1000; num++) {
			
			int i;
            
			for(i=2; i < num; i++) {
				if(num % i == 0) {
					break;
				}
			}
			
			if(i == num) {
				System.out.println(num);
			}
		}
	}
}

 

소수 구하는 알고리즘 2

public class Sosu1 {
	
	public static void main(String[] args) {
		
		int counter = 0;
		int ptr = 0;
		int[] prime = new int[500];
		
		prime[ptr++] = 2;
		
		for(int n=3; n<=1000; n+=2) {
			
			int i;
			
			for(i=1; i < ptr; i++) {
				counter++;
				if(n % prime[i] == 0) {
					break;
				}
			}
			
			if(i == ptr)
				prime[ptr++] = n;
			
		}
		
		for(int i=0; i<ptr; i++) {
			System.out.println("prime[" + i + "] = " + prime[i]);
		}
		
		System.out.println("나눗셈을 수행한 횟수 : " + counter);
		
	}
}

 

- 1번으로 실행하여도 문제는 없지만 1번은 모든 숫자를 대입하여 비교하여 소수를 구한다.

- 2번은 for문을 돌 때마다 n값을 +2 해주었다.(짝수는 무조건 나누어 떨어지기 때문에)

  안쪽포문 밖에있는 if문은 안쪽 포문에서 결과가 나오지 않는다면 나누어 떨어지지 않는것이고 

  안쪽포문의 i++증감자를 통해 자기자신과 같으면(ptr == 1) 소수로 인식하여 배열에 저장한다.