Project Euler – 3

解决 Project Euler – 问题 3。

/**
 * Problem 3
 * Largest prime factor
 * The prime factors of 13195 are 5, 7, 13 and 29.
 * What is the largest prime factor of the number 600851475143 ?
 */

#include <stdio.h>

#include <stdbool.h>
#include <stdlib.h>

#define element_t unsigned long long

/**
 *
 * @NOTE For a * b = c, once a is a divisor(约数) of c, then b is also, and vice versa.
 */
static bool is_prime(element_t num)
{
  for (element_t i = 2; i * i <= num; i++)
  {
    if (num % i == 0) return false;
  }
  return true;
}

static element_t calc_largest_prime(element_t num)
{
  if (is_prime(num))
    return num;
  else
  {
    for (element_t i = 2; i * i <= num; i++)
      if (num % i == 0) return calc_largest_prime(num / i);

    return 1;
  }
}

int main(int argc, char const *argv[])
{
  if (argc != 2) return EXIT_FAILURE;
  element_t n = atoll(argv[1]);

  printf("the largest prime factor of the number %lld is %lld.n",
    n, calc_largest_prime(n));

  return EXIT_SUCCESS;
}

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s