아래 프로그램의 효율을 높이는 문제이다.

int counter=0; int i,n; scanf("%d",&n); for(i = n-1 ; i >= 1 ; i--){ counter++; if ( n % i == 0 ) break; } printf("%d\n",counter); 입력

N 이 입력으로 주어진다. (1 ≤ N ≤ 10^9).

출력

결과를 한 줄에 출력한다.

입출력 예입력 1 출력 0 입력 10 출력 5 입력 27 출력 18



--------------------------------------------------------------------------------------


이 문젠데


#include <iostream>

#include <stdio.h>


using namespace std;


unsigned int PrimeNumber(int n);

bool IsPrimeNumber(int n);


int main() {

unsigned int n, max_divisor, i = 1;

cin << n;


if (n == 1) {

cout << 0;

return 0;

}


while (1) {

if (n % PrimeNumber(i) == 0) {

max_divisor = n / PrimeNumber(i);

break;

}

i++;

}

cout <<n - max_divisor;

return 0;

}


unsigned int PrimeNumber(int n) {

int i = 2, count = 0;

while(1) {

if (IsPrimeNumber(i++) == true) count++;

if (count == n) return --i;

}

}

bool IsPrimeNumber(int n) {

unsigned i;

for (i = 2; i < n; i++) if (n % i == 0) return false;

return true;

}


이렇게 짯거든

2, 3, 5, 7, 9 이렇게 작은 소수들부터 시작해서 나눠떨어지면 그 짝인 수를 구해서 (자기 자신을 제외한 약수 중 최대인 약수) 결과 도출하는 방식으로

근데 10^9 자리 수 가서 시간초과 뜨넹 어떻게 더 빠르게 짤 수 있을까 형들