C++,求大数 (p^n-1) 的质因子分解,其中p为素数,n为整数.
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/08/19 09:33:07
C++,求大数 (p^n-1) 的质因子分解,其中p为素数,n为整数.
例如 p=2,n=100.输出 (p^n-1) 的素因子分解.
再如p=3,n=100.输出 (p^n-1) 的素因子分解.
涉及到大数分解的问题!
例如 p=2,n=100.输出 (p^n-1) 的素因子分解.
再如p=3,n=100.输出 (p^n-1) 的素因子分解.
涉及到大数分解的问题!
![C++,求大数 (p^n-1) 的质因子分解,其中p为素数,n为整数.](/uploads/image/z/15128184-48-4.jpg?t=C%2B%2B%2C%E6%B1%82%E5%A4%A7%E6%95%B0+%28p%5En-1%29+%E7%9A%84%E8%B4%A8%E5%9B%A0%E5%AD%90%E5%88%86%E8%A7%A3%2C%E5%85%B6%E4%B8%ADp%E4%B8%BA%E7%B4%A0%E6%95%B0%2Cn%E4%B8%BA%E6%95%B4%E6%95%B0.)
/*
m的p次方减去1等于(m^0+m^1+m^2+...+m^(p-1))*(m-1),
若不考虑(m-1),则剩余部分m^0+m^1+m^2+...+m^(p-1)
可以用m进制数表示,即111111...1111(m),m进制数,有p个1,
然后利用m进制数的除法判断一个数是否能被整除来分解质因数
*/
#include <iostream>
#include <bitset>
#include <ctime>
using namespace std;
bitset<100002> bits;
//找到质数
void set_prim()
{
clock_t start,end;
start=clock();
bits.set(); int i=2,k;
while(true)
{
while(bits[i]==0) {++i; if(i>400) break;}
if(i<100001)
{
for(int j=i;j<100001;j=j+i) {if((i+j)<100001) bits.reset(i+j);}
++i;}
if(i>100000) break;
}
end=clock();
cout<<"找到<100000质数用时"<<(double)(end - start) / CLOCKS_PER_SEC
<<"秒"<<endl;
int counter=0;
for(int i=1;i<100001;++i) {
if(bits[i]) ++counter;
}
cout<<"质数数量是:"<<counter<<endl;
}
//这里只计算100000以下的质因数,
//如果想能分解出更大的质因数,
//可以加大MAXSIZE的值
const int MAXSIZE = 100000;
//定义一个结构体,主要需要它的长度
typedef struct
{
int xx[1000];
int length;
}Sqlist;
//m_num用于将待测试的数存为m进制数,
//arr初始化为11111.11111(m进制,p个),高位在后
//temp1用于临时储存商和余数的m进制数,高位在后
//temp2用于储存商(while循环后的),高位数在前(数组的0位置)
//copy1用于备份arr
//b就是为了实现rev,可有可无
Sqlist m_num,arr,temp1,temp2,copy1,b;
//将数组倒叙
Sqlist& rev(Sqlist& a)
{
b.length=a.length;
for(int i=0;i<a.length;++i)
{
b.xx[i]=a.xx[a.length-i-1];
}
return b;
}
//将十进制数转化为m进制数
void to_m(Sqlist& m_num,int m,int val)
{
int i=0;
while(val>0)
{
m_num.xx[i]=val%m;
++i;
val=val/m;
}
m_num.length=i;
}
//将m进制数(数组)转化为十进制int,
//转化beg到end部分,物理位置
int to_dec(Sqlist& a,int beg,int end,int m)
{
// cout<<"beg="<<beg<<" end="<<end<<" m="<<m<<endl;
int val=0;
int mul=1;
for(int i=beg;i<=end;++i)
{
val+=a.xx[i]*mul;
mul*=m;
}
return val;
}
//m进制数除法,判断是否整除,并得到除后的结果
//如果不整除,arr内容不变
bool division(Sqlist& arr,Sqlist& m_num,int m)
{
temp2.length=0;
for(int i=0;i<arr.length;++i)
copy1.xx[i]=arr.xx[i];
copy1.length=arr.length;
// cout<<"copy is: "<<to_dec(copy1,0,copy1.length-1,m)<<endl;
int site=arr.length-m_num.length;
//类似竖式除法,site记录对齐时最后一个位置
int key=to_dec(m_num,0,m_num.length-1,m);
// cout<<"key= "<<key<<endl;
int val;
int con=0; //记录每次得到的商
int rem=0; //记录每次得到的余数
int len=m_num.length; //记录要除的数的长度(m进制)
int beg=0,end=0; //记录temp2要插入的位置
int counter=0; //没什么用,就是防止第一次除法商为0记录 //下来,其实没有必要,以为arr初始为1111...11111,第一次商
// 必然大于0
//主循环,每循环一次,site减1,就像竖式除法每次后移一位
while(site>=0)
{
val=to_dec(arr,site,arr.length-1,m);
con=val/key; rem=val%key;
if(counter!=0){
if(con==0) //商是0说明不够除,故商0,加一位继续除
{
temp2.length++;
temp2.xx[end]=0;
end++;
--site;
continue;//直接进入while的喜爱一次循环
}
}
counter++;
//把商变为m进制,并存入temp2中,
//高位在前是因为商是一位一位得到的,从高到低向后
to_m(temp1,m,con);
beg=end; end=beg+temp1.length;
temp2.length+=temp1.length;
for(int i=beg;i<end;++i)
{
temp2.xx[i]=temp1.xx[end-i-1];
}
//把余数变为m进制,并写进arr数组,为了下一次竖式除法
to_m(temp1,m,rem);
arr.length=site+temp1.length;
// cout<<"arr's length is: "<<arr.length<<endl;
--site;
int temp_len=temp1.length-1;
for(int i=arr.length-1;i>site;--i)
{
arr.xx[i]=temp1.xx[temp_len];
--temp_len;
}
// cout<<"site is: "<<site<<endl;
// cout<<temp2.length<<endl;
// cout<<"临时结果:"<<to_dec(rev(temp2),0,temp2.length-1,m)<<endl;
}//end while
bool flag=true;
//判断是否为整除,若整除arr变为temp2,否则返回到copy1
for(int i=0;i<arr.length;++i)
if(arr.xx[i]>0)
{
flag=false;
//如果有一位大于0,说明不整除
}
//整除时
if(flag==true){
for(int i=0;i<temp2.length;++i)
{
arr.xx[i]=temp2.xx[temp2.length-i-1];
}
arr.length=temp2.length;
}
//不整除时
else if(flag==false)
{
for(int i=0;i<copy1.length;++i)
{
arr.xx[i]=copy1.xx[i];
}
arr.length=copy1.length;
}
return flag;
}
int bo[MAXSIZE]; //用物理位置表示数,里面存的数据表示
//能分解出该数的个数,0表示不被分解出它
int main()
{
set_prim();
int m,p;
cout<<"m进制数"<<endl;
while(cin>>m>>p)
{
for(int i=0;i<1000;++i)
temp2.xx[i]=0;
for(int i=0;i<20000;++i)
bo[i]=0;
for(int i=0;i<p;++i)
arr.xx[i]=1;
arr.length=p;
int mm=m-1; //这个是m^0+m^1+m^2+...+m^(n-1)还要乘以的m-1
for(int i=2;i<m;++i)//数据较小,直接连续分解
{
while(mm%i==0)
{
bo[i]++;
mm/=i;
}
}
to_m(m_num,m,2);
while(division(arr,m_num,m))
{
++bo[2];
}
for(int i=3;i<MAXSIZE;i+=2)
{
if(bits[i])
{
to_m(m_num,m,i);
while(division(arr,m_num,m)) ++bo[i];
}
}
for(int i=2;i<MAXSIZE;++i)
{
if(bo[i]>0)
{
cout<<bo[i]<<"个"<<i<<" ";
}
}
cout<<endl;
}
}我这个程序只是分解出100000一下的质因数,想要分出更大的,可以相应放大来查找,很容易.也可以去掉bo数组,每次一输出,降低内存使用. 2的19次方-1下面什么都没输出说明它没有小于100000的质因数.
![](http://img.wesiedu.com/upload/9/d9/9d9197b6679c5a07fe22f306d1c48091.jpg)
m的p次方减去1等于(m^0+m^1+m^2+...+m^(p-1))*(m-1),
若不考虑(m-1),则剩余部分m^0+m^1+m^2+...+m^(p-1)
可以用m进制数表示,即111111...1111(m),m进制数,有p个1,
然后利用m进制数的除法判断一个数是否能被整除来分解质因数
*/
#include <iostream>
#include <bitset>
#include <ctime>
using namespace std;
bitset<100002> bits;
//找到质数
void set_prim()
{
clock_t start,end;
start=clock();
bits.set(); int i=2,k;
while(true)
{
while(bits[i]==0) {++i; if(i>400) break;}
if(i<100001)
{
for(int j=i;j<100001;j=j+i) {if((i+j)<100001) bits.reset(i+j);}
++i;}
if(i>100000) break;
}
end=clock();
cout<<"找到<100000质数用时"<<(double)(end - start) / CLOCKS_PER_SEC
<<"秒"<<endl;
int counter=0;
for(int i=1;i<100001;++i) {
if(bits[i]) ++counter;
}
cout<<"质数数量是:"<<counter<<endl;
}
//这里只计算100000以下的质因数,
//如果想能分解出更大的质因数,
//可以加大MAXSIZE的值
const int MAXSIZE = 100000;
//定义一个结构体,主要需要它的长度
typedef struct
{
int xx[1000];
int length;
}Sqlist;
//m_num用于将待测试的数存为m进制数,
//arr初始化为11111.11111(m进制,p个),高位在后
//temp1用于临时储存商和余数的m进制数,高位在后
//temp2用于储存商(while循环后的),高位数在前(数组的0位置)
//copy1用于备份arr
//b就是为了实现rev,可有可无
Sqlist m_num,arr,temp1,temp2,copy1,b;
//将数组倒叙
Sqlist& rev(Sqlist& a)
{
b.length=a.length;
for(int i=0;i<a.length;++i)
{
b.xx[i]=a.xx[a.length-i-1];
}
return b;
}
//将十进制数转化为m进制数
void to_m(Sqlist& m_num,int m,int val)
{
int i=0;
while(val>0)
{
m_num.xx[i]=val%m;
++i;
val=val/m;
}
m_num.length=i;
}
//将m进制数(数组)转化为十进制int,
//转化beg到end部分,物理位置
int to_dec(Sqlist& a,int beg,int end,int m)
{
// cout<<"beg="<<beg<<" end="<<end<<" m="<<m<<endl;
int val=0;
int mul=1;
for(int i=beg;i<=end;++i)
{
val+=a.xx[i]*mul;
mul*=m;
}
return val;
}
//m进制数除法,判断是否整除,并得到除后的结果
//如果不整除,arr内容不变
bool division(Sqlist& arr,Sqlist& m_num,int m)
{
temp2.length=0;
for(int i=0;i<arr.length;++i)
copy1.xx[i]=arr.xx[i];
copy1.length=arr.length;
// cout<<"copy is: "<<to_dec(copy1,0,copy1.length-1,m)<<endl;
int site=arr.length-m_num.length;
//类似竖式除法,site记录对齐时最后一个位置
int key=to_dec(m_num,0,m_num.length-1,m);
// cout<<"key= "<<key<<endl;
int val;
int con=0; //记录每次得到的商
int rem=0; //记录每次得到的余数
int len=m_num.length; //记录要除的数的长度(m进制)
int beg=0,end=0; //记录temp2要插入的位置
int counter=0; //没什么用,就是防止第一次除法商为0记录 //下来,其实没有必要,以为arr初始为1111...11111,第一次商
// 必然大于0
//主循环,每循环一次,site减1,就像竖式除法每次后移一位
while(site>=0)
{
val=to_dec(arr,site,arr.length-1,m);
con=val/key; rem=val%key;
if(counter!=0){
if(con==0) //商是0说明不够除,故商0,加一位继续除
{
temp2.length++;
temp2.xx[end]=0;
end++;
--site;
continue;//直接进入while的喜爱一次循环
}
}
counter++;
//把商变为m进制,并存入temp2中,
//高位在前是因为商是一位一位得到的,从高到低向后
to_m(temp1,m,con);
beg=end; end=beg+temp1.length;
temp2.length+=temp1.length;
for(int i=beg;i<end;++i)
{
temp2.xx[i]=temp1.xx[end-i-1];
}
//把余数变为m进制,并写进arr数组,为了下一次竖式除法
to_m(temp1,m,rem);
arr.length=site+temp1.length;
// cout<<"arr's length is: "<<arr.length<<endl;
--site;
int temp_len=temp1.length-1;
for(int i=arr.length-1;i>site;--i)
{
arr.xx[i]=temp1.xx[temp_len];
--temp_len;
}
// cout<<"site is: "<<site<<endl;
// cout<<temp2.length<<endl;
// cout<<"临时结果:"<<to_dec(rev(temp2),0,temp2.length-1,m)<<endl;
}//end while
bool flag=true;
//判断是否为整除,若整除arr变为temp2,否则返回到copy1
for(int i=0;i<arr.length;++i)
if(arr.xx[i]>0)
{
flag=false;
//如果有一位大于0,说明不整除
}
//整除时
if(flag==true){
for(int i=0;i<temp2.length;++i)
{
arr.xx[i]=temp2.xx[temp2.length-i-1];
}
arr.length=temp2.length;
}
//不整除时
else if(flag==false)
{
for(int i=0;i<copy1.length;++i)
{
arr.xx[i]=copy1.xx[i];
}
arr.length=copy1.length;
}
return flag;
}
int bo[MAXSIZE]; //用物理位置表示数,里面存的数据表示
//能分解出该数的个数,0表示不被分解出它
int main()
{
set_prim();
int m,p;
cout<<"m进制数"<<endl;
while(cin>>m>>p)
{
for(int i=0;i<1000;++i)
temp2.xx[i]=0;
for(int i=0;i<20000;++i)
bo[i]=0;
for(int i=0;i<p;++i)
arr.xx[i]=1;
arr.length=p;
int mm=m-1; //这个是m^0+m^1+m^2+...+m^(n-1)还要乘以的m-1
for(int i=2;i<m;++i)//数据较小,直接连续分解
{
while(mm%i==0)
{
bo[i]++;
mm/=i;
}
}
to_m(m_num,m,2);
while(division(arr,m_num,m))
{
++bo[2];
}
for(int i=3;i<MAXSIZE;i+=2)
{
if(bits[i])
{
to_m(m_num,m,i);
while(division(arr,m_num,m)) ++bo[i];
}
}
for(int i=2;i<MAXSIZE;++i)
{
if(bo[i]>0)
{
cout<<bo[i]<<"个"<<i<<" ";
}
}
cout<<endl;
}
}我这个程序只是分解出100000一下的质因数,想要分出更大的,可以相应放大来查找,很容易.也可以去掉bo数组,每次一输出,降低内存使用. 2的19次方-1下面什么都没输出说明它没有小于100000的质因数.
![](http://img.wesiedu.com/upload/9/d9/9d9197b6679c5a07fe22f306d1c48091.jpg)
设p为素数,n为任意自然数.求证:(1+n)^p-n^p-1 能被p整除.
因子分解是指将一个整数分解为若干个素数的积的过程
设计一个函数,输出整数n的所有素数因子
证明:分解{1+p+.+p^2k}的素数中一定有一个数大于p 或找出反例.(p为素数,k为正整数)
C语言题(因子个数)因子个数(divisors.cpp)求组合数C(n,k)的不同因子的个数.输入格式:第一行为正整数p
证明:m^p+n^p恒等于0(mod p),则m^p+n^p恒等于0(mod p^2),p为奇素数
一个自然数n的标准分解式为n=2r*3p*5,r,p,为非0自然数,求(T)和(S)
求证:(p,p^m-1)=1,p为素数,m为非负整数(注:m为p的次方)
已知m,n.p都是整数,且|m-n|^3+|p-m|^5=1,求|p-m|+|m-n|+2|n-p|的值
已知数列CN,其中C=(2的n次方 + 3的n次方)且数列{C(n+1)-P*CN}是等比,求常数P
p是正整数n的最小素因数,证明:p>n^(1/3),n/p是素数
近世代数 关于素数的p为素数,在0到(p^r)-1中与p^r互素数的数的个数,求详解