Project Euler P3 Largest prime factor 题解

https://projecteuler.net/problem=3

考虑暴力，于是 TLE。

从 (sqrt{n}) 开始枚举，判断其素性及其整除性。

#include<bits/stdc++.h>
using namespace std;
bool prime(int x) {
	for(int i=2;i*i<=x;i++)
	    if(x%i==0)
	        return 0;
	return 1;
}
int main() {
	for(int i=sqrt(600851475143);i>=1;i--) {
		if(600851475143%i==0&&prime(i)) {//判断整除性与素性
			printf("%d
",i);
			return 0;
		}
	}
}