首页 > 代码库 > 素数相关？(有关素数的题持续更新中)x

素数相关？(有关素数的题持续更新中)x

2024-10-06 19:53:40 209人阅读

总时间限制:: 1000ms
内存限制:: 65536kB

描述

已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。

输入

输入只有一行，包含一个正整数 n。

对于60%的数据，6 ≤ n ≤ 1000。
对于100%的数据，6 ≤ n ≤ 2*10^9。

输出

输出只有一行，包含一个正整数 p，即较大的那个质数。

样例输入

样例输出

7
唯一分解定理：

根据唯一分解定理，若此题有答案，则输入数据满足有且只有一组质数相乘=n

所以，i从2循环到根号n，如果n%i==0，则n/i为答案

也就是说，n=质数a*质数b，n没有其他的分解

证明：

假设还有另外一组分解c*d

那么c*d分解质因数的结果与a*b相同

又因为a、b是质数

所以a*b分解质因数=a*b

所以c=a，d=b

即只有一种分解

c++代码实现：

#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;int n;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0 || x==1) return 0;    int j=3;    while(j<=sqrt(x)&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}int main(){    scanf("%d",&n);    int t=sqrt(n);//i最大的范围     for(int i=2;i<=t;i++)//因为1不是质数，所以循环从2开始进行     {        if(n%i==0)//如果找到了能够进行整除的i             {//又因为样例说一定满足n 是两个不同的质数的乘积，所以直接输出另外一个数就行            //if(pd(i))//所以由上得：不需要判断第一个数是否能够被模 ,即满足唯一分解定理             {                printf("%d",n/i);                return 0;                            }        }    }    return 0;}

View Code

例题2：

第n小的质数 x

总时间限制:: 1000ms
内存限制:: 65536kB

描述

输入一个正整数n，求第n小的质数。

输入

一个不超过10000的正整数n。

输出

第n小的质数。

样例输入

样例输出

29

一定要注意范围范围范围！！！！
开数组一定要注意！！！！！！

c++代码实现：

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>/*#define M 10001这里！！数组开的不能太小！！！ 上面跟下面选取一个进行改正 */#define M 10002using namespace std;int n;struct Q{    int top;    Q()    {        top=0;    }    int s[M];    void jiajia()    {        top++;    }    int add(int x)    {        s[top]=x;    }}q;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0 || x==1) return 0;    int j=3;    while(j<=sqrt(x)&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}void Q_work(){    q.jiajia();    q.add(2);    for(int i=3;;i++)    {         if(pd(i))        {            q.jiajia();            q.add(i);        }          if(q.top>10000) //因为结束条件是q.top>10000所以需要使用到10001个，所以数组需要开到10002         //if(q.top>=10000) 或者上面不改，改这里         break;      }}int main(){    scanf("%d",&n);    Q_work();    printf("%d",q.s[n]);    return 0;}

View Code

例题3：

1530 大质数

题目描述 Description

小明因为没做作业而被数学老师罚站，之后数学老师要他回家把第n个质数找出来。（1<=n<=100000)

老师随机写了几个数，交给了小明。小明百度找了很久，都没能解决。现在交给聪明的你。请你帮忙！

————————————————————————————————————————————

简单描述：把第n个质数找出来。

输入描述 Input Description

一个正整数n。

（1<=n<=100000)

输出描述 Output Description

第n个质数。

（第1个质数为2，第2个质数为3。）

样例输入 Sample Input

样例1

样例2

样例3

20133

样例输出 Sample Output

样例1

样例2

313

样例3

226381

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace std;int n,ans,js;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0 || x==1) return 0;    int j=3;    while(j<=sqrt(x)&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}void Q_work(){    if(n==1)    {        cout<<"2";        return;    }    js=1;    for(int i=2;js!=n;i++)    {         if(pd(i))        {            ans=i;            js++;        }     }    printf("%d",ans);}int main(){    scanf("%d",&n);    Q_work();    return 0;}

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define M 100001using namespace std;int n;struct Q{    int top;    Q()    {        top=0;    }    int s[M];    void jiajia()    {        top++;    }    int add(int x)    {        s[top]=x;    }}q;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0 || x==1) return 0;    int j=3;    while(j<=sqrt(x)&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}void Q_work(){    q.jiajia();    q.add(2);    for(int i=3;;i++)    {         if(pd(i))        {            q.jiajia();            q.add(i);        }          if(q.top>=n)          break;      }}int main(){    scanf("%d",&n);    Q_work();    printf("%d",q.s[n]);    return 0;}

例题4：

判决素数个数

总时间限制:: 1000ms
内存限制:: 65536kB

描述

输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。

输入

两个整数X和Y（1 <= X,Y <= 10⁵）。

输出

输出一个整数，表示X，Y之间的素数个数（包括X和Y）。

样例输入

1 100

样例输出

这道题很坑！有个大坑！

我做了好多遍

给的数据有可能x>y！！！

给的数据有可能x>y！！！

给的数据有可能x>y！！！

#include<iostream>#include<cstdio>#include<cmath>#define M 100001using namespace std;int n,m,ans;int vis[M];void nots(int start,int end){    //for(int i=2;i<=sqrt(end+0.5);i++)    for(int i=2;i<=sqrt(end)+1;i++)        {        if(vis[i]==0)        {            for(int j=i*2;j<=end;j+=i)            {                vis[j]=1;            }            }    }}int main(){    scanf("%d%d",&n,&m);    if(n>m)    {        int temp=n;        n=m;        m=temp;        //swap(n,m);    }    if(n==m)    {        cout<<"0";        return 0;    }    vis[0]=vis[1]=1;//不是素数    vis[2]=0;    nots(n,m);    for(int i=n;i<=m;i++)    {        if(vis[i]==0)        ans++;    }    cout<<ans;     return 0;}

9f(1)

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define M 100001using namespace std;int n,m,ans;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0||x<2) return 0;    int j=3;    while(j*j<x&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}void Q_work(){    if(n>m)    {        int tmp=n;        n=m;        m=tmp;    }    if(n==m) return;    for(int i=n;i<=m;i++)    {        if(pd(i)) ++ans;    }}int main(){    scanf("%d%d",&n,&m);    Q_work();    printf("%d",ans);    return 0;}

9f(2)

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int x,y,n,t;int main() {    cin>>x>>y;    if(x>y) {//进行交换，使得小数在前         t=x;        x=y;        y=t;    }    for(int i=x; i<=y; i++) {        int p=1;//是否为素数         if(i==1)//特判1不是素数             p=0;        for(int j=2; j*j<=i; j++)//筛法求素数             if(i%j==0) {                p=0;                break;            }        n+=p;//统计个数     }    cout<<n;//while(1);    return 0;}

例题5：

codevs 1702 素数判定2

题目描述 Description

一个数，他是素数么？

设他为P满足(P<=2^63-1)

输入描述 Input Description

输出描述 Output Description

Yes|No

样例输入 Sample Input

样例输出 Sample Output

Yes

数据范围及提示 Data Size & Hint

算法导论——数论那一节
注意Carmichael Number

分类标签 Tags 点此展开

#include <bits/stdc++.h>using namespace std;typedef long long ll;//恩，高深int num[]={2,3,5,7,11,13,17,19};int cnt=8;ll mod_mul(ll a,ll b,ll mod) // get the answer to a*b%n {    ll res=0;    while(b){        if (b&1) res=(res+a)%mod;        a=(a+a)%mod;        b>>=1;        }    return res;}ll mod_exp(ll a,ll b,ll n) // get the ans to a^b%n {    ll res=1;    while(b){        if (b&1) res=mod_mul(res,a,n);        a=mod_mul(a,a,n);        b>>=1;        }    return res;}int check(ll n){    if (n==2) return 1;    for (int i=0;i<8;i++) if (n==num[i]) return 1;    if (n==1) return 0;    if (!(n&1)) return 0;      int k=0; ll x;    ll u=n-1;  ll pre;    while(!(u&1)){ k++; u>>=1;}    for (int i=0;i<cnt;i++){        x=num[i];         x=mod_exp(x,u,n); // 费马小定理 a^(p-1)%p==1；         pre=x;        for (int j=0;j<k;j++){            x=mod_mul(x,x,n);  // add delete                if (x==1&&pre!=1&&pre!=n-1) return 0; // if last pre == 1 then x must == 1 else x==p-1;             pre=x;    // second check the x of x^2%p=1 if 1 or p-1;             }        if (x!=1) return 0;        }    return 1;}int main(){    ll n;    cin>>n;    if (check(n)) cout<<"Yes";    else cout<<"No";    return 0;}

View Code

例题6：

孪生素数2

题目描述 Description

如m=100,n=6

则将输出100以内的所有相差6的孪生素数：如，

5　11

7　13

....

83　89

请按此规律输出数与数之间用半角空格区分，每一对一行．

输入描述 Input Description

第一行输入一个整数数m为一个范围(如１００)

第二行输入一个整数k为目标孪生素数的公差(如６)

输出描述 Output Description

每行输出一对，最后一行输出：Total Is:？(？表示总共有几对这样的数，如果不存在则输出Total Is:0)

样例输入 Sample Input

例如１：

50　2

例如２：

100 90

例如３：

200　199

样例输出 Sample Output

例如１：

3 5
5 7
11 13
17 19
29 31
41 43
Total Is:6

例如２：

7 97
Total Is:1

例如３：

Total Is:0

数据范围及提示 Data Size & Hint

m<=5000

分类标签 Tags 点此展开

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define M 5005using namespace std;int n,k,js;int vis[M];int pd(int x){    if(!vis[x]) return 1;    else return 0;}void works(int end){    vis[0]=vis[1]=1;    for(int i=2;i<=sqrt(end+0.5);i++)        {        if(vis[i]==0)        {            for(int j=i*2;j<=end;j+=i)            {                vis[j]=1;            }            }    }}int main(){    scanf("%d",&n);    scanf("%d",&k);    works(n);    for(int i=1;i<=n;i++)    {        if(i+k<=n&&pd(i)&&pd(i+k))        {            cout<<i<<" "<<i+k<<endl;            js++;        }    }    cout<<"Total Is:"<<js;    return 0;}

View Code

例题7：

1031 质数环

题目描述 Description

一个大小为N(N<=17)的质数环是由1到N共N个自然数组成的一个数环，数环上每两个相邻的数字之和为质数。如下图是一个大小为6的质数环。为了方便描述，规定数环上的第一个数字总是1。如下图可用1 4 3 2 5 6来描述。若两个质数环，数字排列顺序相同则视为本质相同。现在要求你求出所有本质不同的数环。

输入描述 Input Description

只有一个数N，表示需求的质数环的大小。如：

输出描述 Output Description

每一行描述一个数环，如果有多组解，按照字典序从小到大输出。如：

样例输入 Sample Input

样例输出 Sample Output

1 4 3 2 5 6

1 6 5 2 3 4

数据范围及提示 Data Size & Hint

n<=17

分类标签 Tags 点此展开

#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<cmath>#include<algorithm>#include<cstdlib>using namespace std;bool b[18]= {0};int a[18]= {0},n;int vis[999];void works(int end){    vis[0]=vis[1]=1;    for(int i=2;i<=sqrt(end+0.5);i++)        {        if(vis[i]==0)        {            for(int j=i*2;j<=end;j+=i)            {                vis[j]=1;            }            }    }}bool pd(int x,int y) { //判断和是否为素数；    int i=x+y;//代表和     if(!vis[i]) return 1;    else return 0;}int print() { //输出；    for(int j=1; j<=n; j++)        cout<<a[j]<<" ";    cout<<endl;}int search(int t) {    int i;    for(i=2; i<=n; i++) {        if((!b[i])&&pd(a[t-1],i)) { //!b[i]是说b[i]没有被使用过//判断与前一个数是否构成素数及该数是否可用            a[t]=i;            b[i]=1;//将使用过的赋值为1；            if(t==n&&pd(a[n],1))                print();            else search(t+1);            b[i]=0;//还原；        }    }}int main() {    cin>>n;    a[1]=1;    b[1]=1;    if(n%2==1) {        cout<<endl;        return 0;    } else    {        works(60);//第十七个素数为59         search(2);    }    return 0;}

View Code

例题8：

luogu P1217 [USACO1.5]回文质数 Prime Palindromes

题目描述

因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。

写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;

输入输出格式

输入格式：

第 1 行: 二个整数 a 和 b .

输出格式：

输出一个回文质数的列表，一行一个。

输入输出样例

输入样例#1：

5 500

输出样例#1：

5711101131151181191313353373383

说明

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.

Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

题目翻译来自NOCOW。

USACO Training Section 1.5

产生长度为5的回文数:

for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数

     for (d2 = 0; d2 <= 9; d2++) {         for (d3 = 0; d3 <= 9; d3++) {           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)         }     } }

思路:

　　如题。

代码:

#include <iostream>#include <cstdio>#include <cmath>using namespace std;const int N = 1e8 + 1;const int M = 6e7;int a,b;int pd(int x){    if(x==2||x==3) return 1;    if(x%2==0 || x==1) return 0;    int j=3;    while(j<=sqrt(x)&&x%j!=0) j+=2;    if(x%j==0) return 0;    else return 1;}void get_hui(){    int num;    int aa=a;    while(aa<10)     {        if(pd(aa) && aa>=a) printf("%d\n",aa);        aa++;    }    for(int i=1;i<=9;i+=2)    {        num=i*10+i;        if(num>b) return;        if(num>=a && pd(num)) printf("%d\n",num);    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            num=i*100+j*10+i;            if(num>b) return;            if(num>=a && pd(num)) printf("%d\n",num);        }    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            num=i*1000+j*100+j*10+i;            if(num>b) return;            if(num>=a && pd(num)) printf("%d\n",num);        }    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            for(int k=0;k<=9;k++)            {                num=i*10000+j*1000+k*100+j*10+i;                if(num>b) return;                if(num>=a && pd(num)) printf("%d\n",num);            }        }    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            for(int k=0;k<=9;k++)            {                num=i*100000+j*10000+k*1000+k*100+j*10+i;                if(num>b) return;                if(num>=a && pd(num)) printf("%d\n",num);            }        }    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            for(int k=0;k<=9;k++)            {                for(int w=0;w<=9;w++)                {                    num=i*1000000+j*100000+k*10000+w*1000+k*100+j*10+i;                    if(num>b) return;                    if(num>=a && pd(num)) printf("%d\n",num);                }            }        }    }    for(int i=1;i<=9;i+=2)    {        for(int j=0;j<=9;j++)        {            for(int k=0;k<=9;k++)            {                for(int w=0;w<=9;w++)                {                    num=i*10000000+j*1000000+k*100000+w*10000+w*1000+k*100+j*10+i;                    if(num>b) return;                    if(num>=a && pd(num)) printf("%d\n",num);                }            }        }    }}int main(){    scanf("%d%d",&a,&b);    get_hui();    return 0;}

View Code

（不定更新）


最后给出大佬直通站：

http://blog.sina.com.cn/s/blog_4b5210840100cm4r.html

素数相关？(有关素数的题持续更新中)x

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 素数相关？(有关素数的题持续更新中)x

素数相关？(有关素数的题持续更新中)x

第n小的质数 x

判决素数个数

分类标签 Tags 点此展开

分类标签 Tags 点此展开

分类标签 Tags 点此展开

luogu P1217 [USACO1.5]回文质数 Prime Palindromes

题目描述

输入输出格式

输入输出样例

说明

看完仍有疑问？有类似问题直接问程序猿