Project Euler – 7

解决 Project Euler – 问题 7。

/**
 * Problem 7
 * 10001st prime
 *
 * By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
 * What is the 10 001st prime number?
 */

#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(const element_t num)
{
  for (element_t i = 2; i * i <= num; i++)
  {
    if (num % i == 0) return false;
  }
  return true;
}

/** calc prime number by index */
static element_t calc_prime(const element_t index)
{
  element_t count = 0;
  element_t num = 1;          /* NOTE: start from 2(++1) */
  do
  {
    count += is_prime(++num) ? 1 : 0;
  } while (index - count);
  return num;
}

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

  printf("the %llust prime number is %llu.n",
    index, calc_prime(index));

  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