2011-08-09 08:36:02Morris
d705. 判断质数（二）
d705. 判断质数（二）
/* Problem: d705 "判断质数（二）" from 判断质数系列 */
/* Language: C */
/* Result: AC (112ms, 140KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-08 07:30:50 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
long long Ans = 1, t = x;
while(n) {
if(n&1)
Ans *= t, Ans %= mod;
t *= t, t %= mod, n >>= 1;
}
return (int)Ans;
}
int JudgePrime(int n) {
if(n == 2 || n == 3) return 1;
if(n == 1) return 0;
if(!(n&1)) return 0;
int a, x, flag = 1, t;
for(a = 0; a < 2; a++) {
x = rand()%(n-4)+2;
t = Pow(x, n-1, n);
if(t != 1) return 0;
}
return 1;
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
main() {
int n;
while(ReadInt(&n) && n) {
if(JudgePrime(n)) puts("0");
else puts("1");
}
return 0;
}
內容 ：
判断质数的题目大家都做得太累了吧...是不是很容易AC呢？
如果你能够轻而易举AC题目 d709: 判断质数（一） 的话，那么请来挑战一下这个判断质数系列！
輸入說明
：
每行读入一个要判断的数N（1<=N<=2147483647）。
测资最多有100000行。
当N=0时，退出程序。
輸出說明
：
如果N是质数则输出 0 ，否则输出 1 。
範例輸入 ：
1 2 3 4 0
範例輸出 ：
1 0 0 1
提示
：
这几组判断质数系列的题目，看似都差不多、都很吓人（也许吧），其实所考察的算法大大不一样！
不要认为这又是翻版的 “求幂系列题”！
我是不会浪费大家的时间的！
//由于本题的测资把一般算法刚好卡在1s之外，这里希望大家挑战一下极限，让自己的程序写得更有效率，进入1s以内吧！
//本人的程序进入了4xx ms啦！大家来赶超吧``
出處
：
判断质数系列
(管理：liouzhou_101)
作法 : 隨機判斷
以下由 liouzhou_101 講述
/**********************************************************************************/作法 : 隨機判斷
以下由 liouzhou_101 講述
其实进入1s必须要用随机化（random）算法！ 但是这个随机化算法的正确率必须很高很高>99% 先说说以下定理： 若n是质数，那么对于所有的整数x∈[2,n)有 x^(n-1)=1(mod n) 反之，很少有非质数的数符合这个条件。//当然1和2要特殊判断。 然后的就是用随机数算法，不断随机出k个数∈[2,n)，并判断到底是不是x^(n-1)=1(mod n) 若不是，则说明这个数不是质数。 若对于所有k个数都符合，那么我们说这个数就有可能是质数。 在程序中，若某个数极有可能是质数，我们就认为它的质数。 据我的仔细推敲，当k=15时，效率和正确率都很高。 但为了让程序更快，k=5就行了。
我下面只有取 k = 2
/* Problem: d705 "判断质数（二）" from 判断质数系列 */
/* Language: C */
/* Result: AC (112ms, 140KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-08 07:30:50 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
long long Ans = 1, t = x;
while(n) {
if(n&1)
Ans *= t, Ans %= mod;
t *= t, t %= mod, n >>= 1;
}
return (int)Ans;
}
int JudgePrime(int n) {
if(n == 2 || n == 3) return 1;
if(n == 1) return 0;
if(!(n&1)) return 0;
int a, x, flag = 1, t;
for(a = 0; a < 2; a++) {
x = rand()%(n-4)+2;
t = Pow(x, n-1, n);
if(t != 1) return 0;
}
return 1;
}
int ReadInt(int *x) {
static char c, neg;
while((c = getchar()) < '-') {if(c == EOF) return EOF;}
neg = (c == '-') ? -1 : 1;
*x = (neg == 1) ? c-'0' : 0;
while((c = getchar()) >= '0')
*x = (*x << 3) + (*x << 1) + c-'0';
*x *= neg;
return 1;
}
main() {
int n;
while(ReadInt(&n) && n) {
if(JudgePrime(n)) puts("0");
else puts("1");
}
return 0;
}