[JAVA] 백준 1016번 : 제곱 ㄴㄴ 수

 

---

 

• 코드

실패 코드 : 일단 원하는대로 값은 나오는데 시간 초과가 뜬다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long min = Long.parseLong(st.nextToken());
		long max = Long.parseLong(st.nextToken());
		
		int count = (int) (max-min+1);
		for(int j=(int) min;j<=max;j++) {
			for(int i=2;i*i<=max;i++) {
				if(j%(i*i)==0) {
					count--;
					break;
				}
			}
		}
		
		System.out.println(count);
				
    }
}

 

 

정답 코드  : 에라토스테네스의 체 방식과 비슷한 방식으로 풀어 보았다.

                i가 2일때부터 i*i값을 가져와서 min값에서 가장 가까운 i*i로 떨어지는 값을 찾는다. 찾는 방법이 힘들었는데 찾은 식은 min +(index - (min%index))%index이다. 여기서 index는 i*i 값이다. i*i로 나누어 떨이지는 값들을 min부터 max값까지 모두 체크하고 i+1하고 해당 작업을 반복해주는 방식으로 하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		long min = Long.parseLong(st.nextToken());
		long max = Long.parseLong(st.nextToken());
		
		int range = (int) (max-min+1);
		
		boolean [] check = new boolean[range];
		
		for(long i=2;i*i<=max;i++) {
			long index = i*i;
			long startNumber = min +(index - (min%index))%index;
			
			for(long j = startNumber; j<=max;j+=index) {
				check[(int) (j-min)] = true;
			}
		}
		
        int count = 0;
        for(int i = 0; i < range; i++){
            if(!check[i])
                count++;
        }
        System.out.println(count);
				
    }
}