5.소수(에라토스테네스 체)/6.뒤집은 소수

수업 내용이지만 배수 찾는 건 늘 /로 활용하였었는데 여기 방법은 좀 신선했다.

결국 소수 찾기 못 풀긴했음

---

문제 

* 소수(에라토스테네스 체)
* 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
* 만약 20이 입력되면 1부터 20까지의 소수는 2,3,5,7,11,13,17,19로 총 8개입니다.

n번까지의 인덱스 생성을 위해 배열을 n+1개 만든다.

int[] ch = new int[n+1];

각각의 배열에 담긴 숫자를 0으로 통일한후, for문을 돌려 배수를 각각 삭제 (삭제할 땐 0을 다른 숫자로 변경)

for문 돌면서 숫자가 0일때마다 cnt++을 해준다.

j+i : 배수 표현 : 배수일 때마다 배열 값 1로 변경

for(int i=2; i<=n; i++){
    if(ch[i]==0){
        cnt++;
        for(int j=i; j<=n; j=j+i) ch[j]=1;
    }
}

 

 

---

문제2

숫자에 대해 소수 판단 방법 

        if(num==1) return false;
        for(int i=2;i<num;i++){
            //약수 존재
            if(num%i==0) return false;
        }
        return true;

5번 문제도 이렇게 풀수있지않을까 도전해보기

 

숫자 뒤집기

int t= tmp%10;
res = res*10+t;
tmp=tmp/10;

 

% 나머지 

/ 몫