工学1号馆

home

« | 返回首页 | »

Project Euler 3–Largest prime factor

By Wu Yudong on June 18, 2017

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

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)