1、ACM数论问题一、数论中的著名问题： 高斯曾经说过 “ 数学是科学的皇后，数论是数学中的皇冠 ” 。因此，数学家都喜欢把数论中一些悬而未决的疑难问题叫做 “ 皇冠上的明珠 ” ，以鼓励人们去 “ 摘取 ” 。 1.哥德巴赫猜想： 任一充分大的偶数都可以表示成为一个素因子个数不超过 a个的数与另一个素因子不超过b个的数之和，记作 “a+b” （欧拉版本）。 1966年陈景润证明了任何一个大偶数都可表示成一个素数与另一个素因子不超过 2个的数之和 ” 。2.费马大定理： 当整数 n2时，关于 x,y,z的不定方程xn+yn=zn无正整数解 (x=0或 y=0不在考虑之列 ).1994年德国数学家维
2、尔斯解决了这个问题，并获得了沃尔夫奖 .3. 费马小定理： 假如 a是一个整数， p是一个素数，则1、素数的概念和性质定义： 设 a,b为整数，且 b0. 如果存在整数 q，使得a=bq，那么称 b整除 a，记作 b|a，并且称 b是 a的因数，a是 b的倍数 . 如果这样的整数 q不存在，就称 b不整除 a，记作 b | a .v素数（ prime）和合数（ compound） :如果一个整数 p只有 1和 p两个因子，则 p为素数，不为素数的其它数为合数。v性质：v(1)每个正整数 n除 1外的最小正因数 p是一个素数 .v(2)若 p为素数， p|ab，则 p|a或 p|bv(3)如果大
3、于 1的整数 a不能被所有不超过 的素数整除，那么 a一定是素数。1、素数的概念和性质问题：1、给一个数 n，小于 n的素数有哪些？2、给一个数 n，如何判断 n是不是素数？v最一般的求解 n以内素数的算法。复杂度是o(n*sqrt(n)，适合 n很小num = 0; for(i=2; isqrt(i) ) primenum+ = i; 1、素数的概念和性质v当 n很大的时候，比如 n=10,000,000时，n*sqrt(n)30,000,000,000,数量级相当大v思考如何改进？1、素数的概念和性质2、素数筛法v最简单的素数筛法 开一个大的 bool型数组 p，大小就是 n+1就可以了 .先把所有的下标为奇数的标为 true,下标为偶数的标为 false. 把奇数的倍数设为 false. v改进的素数筛法 bool型数组里面只存奇数不存偶数。如定义 pN,则 0表示 3， 1表示 5， 2表示 7， 3表示 9.。如果 p0为 true,则表示 3为素数。 p3为 false意味着 9是合数，每个单元代表的数是 2*i+3。2i+3|pi+xpi2、素数筛法Eraosthenes（爱拉托斯尼）筛法：每次求出一个新的素数，就把 n以内的它的所有倍数都筛去。
