[백준 9753] 짝 곱 (C++/Java)

- C++ 

1. 메모리 : 3728KB / 시간 : 832ms

#include <iostream>
#include <vector>
#include <algorithm>
#define max 100000
using namespace std;
vector<int> v;
bool pm[50001];
int main(void){
  cin.tie(0);  cout.tie(0);
  ios_base ::sync_with_stdio(false);
 
  int n; cin >> n;
 
  // 소수 찾기
  for (int i = 2; i * i <= max/2; i++){
    if (!pm[i]){
      for (int j = i * i; j <= max/2; j += i)
        pm[j] = true;
    }
  }
 
  for(int i=2; i<50000; i++){
    for(int j=i+1; j<50000; j++){
      if(i*j<=max+1 && pm[i]==false && pm[j]==false){
        v.push_back(i*j);
      } 
    }
  }
 
  sort(v.begin(), v.end());
 
  
  // target 넘버 찾기
  while (n--) {
    int target;
    cin >> target;
 
    int start = 0, end = v.size(), mid = 0;
    int ans = 0;
 
    while (start <= end){
      mid = (start + end) / 2;
 
      if (v[mid] == target){
        ans = target;
        break;
      } else if (target < v[mid]) {
        end = mid - 1;
        ans = v[mid];
      } else{
        start = mid + 1;
      }
    }
    cout << ans << "\n";
  }
 
  return 0;
}

 

 

2. 메모리 : 3792kb / 시간 : 24ms

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#define max 100000
using namespace std;
vector<int> v;
vector<int> arr;
bool pm[50001];
int main(void){
  cin.tie(0);  cout.tie(0);
  ios_base ::sync_with_stdio(false);
 
  int n; cin >> n;
 
  // 소수 찾기
  for (int i = 2; i * i <= max/2; i++){
    if (!pm[i]){
      for (int j = i * i; j <= max/2; j += i)
        pm[j] = true;
    }
  }
 
  for(int i=2; i<=max/2; i++){
    if(!pm[i]) arr.push_back(i);
  }
 
  for(int i=0; i<arr.size(); i++){
    for(int j=i+1; j<arr.size(); j++){
      if(arr[i]*arr[j]<=max+1) v.push_back(arr[i]*arr[j]);
    }
  }
 
  sort(v.begin(), v.end());
 
  
  // target 넘버 찾기
  while (n--){
    int target; cin >> target;
 
    int start = 0, end = v.size()-1, mid = 0;
    int ans = 0;
 
    while (start <= end){
      mid = (start + end) / 2;
 
      if (v[mid] == target){
        ans = target;
        break;
      } else if (target < v[mid]){
        end = mid - 1;
        ans = v[mid];
      } else{
        start = mid + 1;
      }
    }
    cout << ans << "\n";
  }
 
  return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main{
    static boolean[] pm = new boolean[50001];
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int tc = Integer.parseInt(br.readLine());
 
        // 소수 찾기
        for(int i=2; i*i<=50000; i++){
            if(!pm[i]){
                for(int j=i*i; j<=50000; j+=i)
                    pm[j]=true;
            }
        }
 
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for(int i=2; i<=50000; i++){
            if(pm[i]==false) 
                temp.add(i);
        }
 
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<temp.size(); i++){
            for(int j=i+1; j<temp.size(); j++){
                if(temp.get(i)*temp.get(j)<= 100001) {
                arr.add(temp.get(i) * temp.get(j));
                }
            }
        }
 
       Collections.sort(arr);
 
        StringBuilder sb = new StringBuilder();
        
        // target 넘버 찾기
        for(int i=0; i<tc; i++){
            int target = Integer.parseInt(br.readLine());
 
            int start=0, end=arr.size()-1, mid=0;
            int ans=0;
 
            while(start<=end){
                mid = (start+end)/2;
 
                if(arr.get(mid) == target){
                    ans = target;
                    break;
                }
                else if(target < arr.get(mid)){
                    end = mid-1;
                    ans = arr.get(mid);
                } else {
                    start = mid+1;
                }
            } 
            sb.append(ans).append("\n");
        }
        System.out.print(sb); 
        
    }
}