슥이블로그

소수 구하는 알고리즘 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) 소수로 인식하여 배열에 저장한다.

String 클래스는 많은 생성자와 메서드를 제공

기수 변환

- 10진수 정수를 n진수 정수로 변환하려면 정수를 n으로 나눈 나머지를 구하는 동시에 그 몫에 대해 나눗셈을 반복.

- 이 과정을 몫이 0이 될 때까지 반복하고, 이런 과정으로 구한 나머지를 거꾸로 늘어 놓은 숫자가 기수로 변환한 숫자.