题目链接:http://poj.org/problem?id=1811
题目意思:给出一个数判断是否是素数,若不是素数,求出最小质因子
费马小定理:若p是素数,则有 a^(p-1) =1 (mod p ) , 1<=a<=n-1。
二次探测定理: 若p是素数,对于 0<x<p ,有 x^2= 1 ( mod p) 的解 x=1, p-1。
首先是素数的测试,根据费马小定理和二次探测定理对素数进行测试
整数分解: n为待分解数,
1 找出两个数x,y ,求d=gcd( y - x, n)
2 若1<d< n 返回d; 若y==x 返回n;
当分解出一个约数之后,用分治的方法求出最小质因子
代码如下:
//============================================================================
// Name : poj1811.cpp
// Author : ssslpk
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define int64 long long
#define TIME 12
#define inf 1e10
using namespace std;
int64 minn;
int64 gcd(int64 a,int64 b){return b? gcd(b,a%b):a;}
int64 mod_mult(int64 a,int64 b,int64 n)// 求 (a * b)%n
{
int64 s=0;
a=a%n;
while(b)
{
if(b&1) s=(s+a)%n;
a<<=1;
a=a%n;
b>>=1;
}
return s;
}
int64 mod_exp(int64 a,int64 b,int64 n)// 求(a ^ b)%n
{
int64 d=1;a%=n;
while(b>=1)
{
if(b&1)d=mod_mult(d,a,n);
a=mod_mult(a,a,n);
b>>=1;
}
return d;
}
bool witness(int64 a, int64 n)
{
int64 m, x, y;
int64 i, j = 0;
m = n - 1;
while (m % 2 == 0)
{
m = m >> 1;
j++;
}
x = mod_exp(a, m, n);
for (i = 1; i <= j; i++) {
y = mod_exp(x, 2, n);
if ((y == 1) && (x != 1) && (x != n - 1))
return false;
x = y;
}
return y==1;
}
bool miler(int64 n)
{
if(n==2)return true;
if(n%2==0 || n==1)return false;
for(int i=0;i<TIME;i++)
{
int64 x=rand()%(n-1)+1;
// int64 x=rand()*(n-2)%RAND_MAX+1;
if(! witness(x,n))return false;
}
return true;
}
int64 Pollard(int64 n,int64 c)
{
int64 i,k,x,y,d;
srand(time(NULL));
i=1;k=2;
x=rand()%n;
y=x;
while(1)
{
i++;
x=(mod_mult(x,x,n)+c)%n;
d=gcd(y-x,n);
if(d>1 && d<n )return d;
if(y==x)return n;
if(i==k)
{
y=x;
k=k<<1;
}
}
}
void find_min(int64 n,int64 c)
{
if(n==1)return;
if(miler(n))
{
if(n<minn)minn=n;
return ;
}
int64 m=Pollard(n,c--);
find_min(m,c);
find_min(n/m,c);
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
int64 n;
scanf("%lld",&n);
if(miler(n))printf("Prime\n");
else
{
minn=inf;
find_min(n,240);
printf("%lld\n",minn);
}
}
return 0;
}
分享到:
相关推荐
【标签】"POJ 3126 Prime Path" 指明了问题的关键元素:POJ是一个在线编程平台,3126是这道题目的编号,Prime Path则揭示了问题的核心,即寻找素数路径。 【详细说明】在解决"Prime Path"这个问题时,我们需要掌握...
"POJ1035-Spell checker 测试数据" 是一个与编程竞赛相关的主题,其中“POJ”是北京大学主办的在线编程平台Problem Online Judge的缩写,它提供了各种算法题目供参赛者挑战。"Spell checker" 指的是这个题目所涉及的...
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...
"西北工业大学POJ试题C++答案代码+课程设计"这一标题表明了资源的主要内容,涉及两个核心部分:一是西北工业大学的编程竞赛(POJ,Problem Oriented Judge System)的C++解题代码,二是与这些题目相关的课程设计。...
《POJ1207-The 3n + 1 problem》是北京大学在线编程平台POJ上的一道经典算法题目,其主要涉及的知识点是数论和动态规划。本题目的核心是解决著名的“Collatz Conjecture”问题,也被称为“3n+1猜想”。 3n+1猜想是...
《POJ1472-即时复杂性:深入解析与测试数据详解》 POJ1472,名为“Instant Complexity”,是源自1997年Southwestern European Regional Contest的一道算法竞赛题目。该问题涉及计算机科学中的算法设计与分析,特别...
【标题】"POJ3733-Changing Digits【DFS+强剪枝】"是一个来自北京大学在线评测系统POJ的编程题目,该题目主要涉及深度优先搜索(DFS)算法和强剪枝策略。在算法竞赛和编程挑战中,这类问题通常要求参赛者通过编写...
《POJ3009-Curling 2.0:深度优先搜索、向量、回溯与剪枝的综合应用》 北京大学在线编程平台上的POJ3009题目名为"Curling 2.0",它是一道涉及到算法与数据结构的复杂问题,主要考察了参赛者对深度优先搜索(DFS)、...
“AC代码”是指在POJ平台上成功通过测试用例的代码,通常包括C、C++、Java等语言的实现。AC状态代表代码正确实现了题目的要求,并且在规定的时间和内存限制内完成了运行。通过阅读和分析这些代码,可以学习到不同...
【标签】"POJ 3292 Semi-prime H-numbers"是该问题的标签,它强调了问题来源(POJ平台)、问题编号(3292)以及问题的核心概念——半素数和H-Numbers。 半素数是指由两个不同的质数相乘得到的自然数,例如6(2×3)...
+ poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
《POJ3026-Borg Maze:BFS与Prim算法的应用解析》 在计算机科学领域,图论是解决问题的重要工具之一,而BFS(广度优先搜索)和Prim算法则是其中的两种经典算法。本篇文章将围绕北大POJ3026题目“Borg Maze”来探讨...
综上所述,解答"POJ2739 - Sum of Consecutive Prime Numbers"这一题目,需要掌握素数的定义、素数检测方法、算法设计思路,以及高效的代码实现和优化技巧。通过解题报告和AC代码,我们可以学习到如何将理论知识应用...
【标题】"POJ1523 - SPF 测试数据"是源于 Greater New York 2000 年编程竞赛中的问题H,这个题目在ACM(国际大学生程序设计竞赛)领域内颇具代表性。SPF全称为Shortest Path First,通常指的是寻找图中最短路径的一...
标题“POJ3373-Changing Digits【DFS+强剪枝】”涉及的是一个编程竞赛中的问题,这个问题在北大POJ(北京大学在线评测系统)平台上被提出。"Changing Digits"是一个算法挑战,而解决方案是通过深度优先搜索(DFS)...
【标题】"POJ 1027 官方测试数据"是指的编程竞赛网站POJ(Programming Online Judge)上的一道题目1027的官方提供的测试用例。POJ是一个面向全球程序员的在线判题系统,它允许参赛者提交代码并运行在服务器上,以...
至于"压缩包子文件的文件名称列表"中提到的"POJ1724-ROADS 测试数据",这通常是一个包含了多个测试用例的文件集合,每个文件代表一个特定的输入,可能有对应的预期输出文件。这些文件的格式可能为文本,其中包含数字...
poj 3361 Gaussian Prime Factors.md