哥德巴赫猜想的程序验证

任何一个充分大的偶数都可以表示为两个素数之和
服务器君一共花费了118.768 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

Timus Online Judge 网站上有这么一道题目:1356. Something Easier。这道题目的输入是一组  2 到 109 之间整数,对于每个输入的整数,要求用最少个数的素数的和来表示。这道题目的时间限制是 1 秒。

我们知道著名的哥德巴赫猜想是:任何一个充分大的偶数都可以表示为两个素数之和。

于是我们有以下的 C 语言程序:

// http://acm.timus.ru/problem.aspx?space=1&num=1356
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
// http://en.wikipedia.org/wiki/Prime_number_theorem
#define PRIME_MAX 10000
#define PRIME_COUNT 1229
 
typedef unsigned long long U8;
typedef char bool;
 
const bool true = 1;
const bool false = 0;
 
// http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
bool* getSieve(int max)
{
  static bool sieve[(PRIME_MAX >> 1) + 1];
  int i, j, imax = sqrt(max);
  for (i = 3; i <= imax; i += 2)
    if (!sieve[i >> 1])
      for (j = i * i; j <= max; j += i << 1) sieve[j >> 1] = true;
  return sieve;
}
 
int* getPrimes(int max)
{
  static int primes[PRIME_COUNT + 1];
  bool *sieve = getSieve(max);
  int i, j = 0;
  for (primes[j++] = 2, i = 3; i <= max; i += 2)
    if (!sieve[i >> 1]) primes[j++] = i;
  return primes;
}
 
U8 modMultiply(U8 a, U8 b, U8 m)
{
  return a * b % m;
}
 
U8 modPow(U8 a, U8 b, U8 m)
{
  U8 v = 1, p;
  for (p = a % m; b > 0; b >>= 1, p = modMultiply(p, p, m))
    if (b & 1) v = modMultiply(v, p, m);
  return v;
}
 
bool witness(U8 a, U8 n)
{
  U8 n1 = n - 1, s2 = n1 & -n1, x = modPow(a, n1 / s2, n);
  if (x == 1 || x == n1) return false;
  for (; s2 > 1; s2 >>= 1)
  {
    x = modMultiply(x, x, n);
    if (x == 1) return true;
    if (x == n1) return false;
  }
  return true;
}
 
U8 random(U8 high)
{
  // http://www.cppreference.com/wiki/c/other/rand
  return (U8)(high * (rand() / (double)RAND_MAX));
}
 
// http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
// n, an integer to be tested for primality
// k, a parameter that determines the accuracy of the test
bool probablyPrime(U8 n, int k)
{
  if (n == 2 || n == 3) return 1;
  if (n < 2 || n % 2 == 0) return 0;
  while (k-- > 0) if (witness(random(n - 3) + 2, n)) return false;
  return true;
}
 
bool isPrime(int n)
{
  return probablyPrime(n, 2);
}
 
int outEven(int primes[], int n)
{
  int i, p, q;
  for (i = 0; (p = primes[i]) != 0; i++)
    if (isPrime(q = n - p))
      return printf("%d %d", p, q);
  return printf("error:%d", n);
}
 
int main(void)
{
  int t, n, *primes = getPrimes(PRIME_MAX);
  srand(time(NULL));
  scanf("%d", &t);
  while (t-- > 0)
  {
    scanf("%d", &n);
    if (isPrime(n)) printf("%d", n);
    else if ((n & 1) == 0) outEven(primes, n);
    else if (isPrime(n - 2)) printf("2 %d", n - 2);
    else printf("3 "), outEven(primes, n - 3);
    puts("");
  }
  return 0;
}
  • 根据哥德巴赫猜想,充分大的偶数 n = p + q,这里 p <= q 是素数。我们猜测当 n <= 109 时,p < 104。第 8 行就是定义 p 的最大值。
  • 根据素数定理,我们知道 104 以内的素数有 1229 个。第 9 行就是定义程序中要用到的素数的个数。
  • 第 17 到 26 行的 getSieve 函数用埃拉托斯特尼筛法筛选出素数。
  • 第 28 到 36 行的 getPrimes 函数从筛中取出这些素数。
  • 第 38 到 79 行的一系列函数最终是为了 probablyPrime 函数,用于检测素数。请参见我在2010年7月写的随笔:【算法】米勒-拉宾素性检验
  • 第 81 到 84 行的 isPrime 函数调用 probablyPrime 函数来检测素数。
  • 第 86 到 93 行的 outEven 函数对大于 2 的偶数验证哥德巴赫猜想,即输出一对素数 p 和 q。
  • 第 95 到 110 行是 main 函数。其中:
  • 第 103 行处理 n 是素数的情况,直接输出该素数(包括素数 2,所以 outEven 函数处理的偶数肯定大于 2)。
  • 第 104 行对大于 2 的偶数输出一对素数(通过调用 outEven 函数,强哥德巴赫猜想)。
  • 第 105 行处理大于 5 的奇数能够分解为 2 和另外一个素数的和的情况(注意不要遗漏这个情形!)。
  • 第 106 行处理大于 5 的奇数的其他情况,首先输出一个 3,然后调用 outEven 函数处理偶数 n - 3 (弱哥德巴赫猜想)。

上述程序在 Timus Online Judge 网站的运行时间是 0.015 秒。

本文地址:http://www.nowamagic.net/librarys/veda/detail/800,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/800

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《人月神话》 弗雷德里克·布鲁克斯 (作者), 汪颖 (译者)

《人月神话》原文:The Mythical Man-Month: The Essays on Software Engineering, 2nd ed.在软件领域,很少能有像《人月神话》一样具有深远影响力并且畅销不衰的著作。Brooks博士为人们管理复杂项目提供了最具洞察力的见解。既有很多发人深省的观点,又有大量软件工程的实践。本书内容来自Brooks博士在IBM公司System/360家族和OS/360中的项目管理经验。该书英文原版一经面世,即引起业内人士的强烈反响,后又译为德、法、日、俄中等多种语言,全球销量数百万册。确立了其在行业内的经典地位。

更多计算机宝库...