素数优化算法解决

解题思路:主要根据素数的数学特点

注意事项:该编译器采用C99标准，要加头文件使用bool或用内置_Bool

参考代码:

#define  _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

#include<math.h>

#include<stdbool.h>

bool isPrime(int n)

{

if (n <= 3 && n > 1)

{

return n > 1;

}

//不在6的倍数两侧的一定不是素数

if ((n % 6 != 1) && (n % 6 != 5))

{

return false;

}

for (int i = 5; i <= sqrt(n); i += 6)

{

if (n % i == 0 || n % (i + 2) == 0)

{

return false;

}

}

return true;

}

int main() {

int n;

scanf("%d", &n);

for (int i = 2; i <= sqrt(n); i++) {

if (isPrime(i) && isPrime(n / i) && n % i == 0) {

printf("%d", i > n / i ? i : n / i);

break;

}

}

return 0;

}