Wu Yudong's Blog

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

题目大意：

13195的质数因子有5,7,13和29.

600851475143的最大质数因子是多少？

#include<stdio.h>
#include<math.h>
#include<stdbool.h>
#define N 600851475143

bool prim(int n)
{
	int i;
	for (i = 2; i * i <= n; i++) {
		if (n % i == 0)
			return false;
	}
	return true;
}

int main()
{
	long long s = sqrt(N);
	while (s--) {
		if (s % 2 != 0 && prim(s) && (N % s == 0)) {

			printf("%lld\n", s);
			break;
		}
	}
	return 0;
}

Answer:6857
Completed on Tue, 23 Jul 2013, 17:18