首页 > 其他 > 详细

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

时间：2017-06-15 21:23:37      阅读：600      评论：0      收藏：0      [点我收藏+]
总时间限制: 
1000ms
 
内存限制: 
65536kB
描述

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

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

对于60%的数据，6 ≤ n ≤ 1000。
对于100%的数据，6 ≤ n ≤ 2*10^9。
输出
输出只有一行，包含一个正整数 p，即较大的那个质数。
样例输入
21
样例输出
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小的质数。
样例输入
10
样例输出
29

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

c++代码实现：
技术分享 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
/*
#define M 10001这里！！数组开的不能太小！！！ 
上面跟下面选取一个进行改正 
*/
#define M 10002

using 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

样例2

65

样例3

20133

样例输出 Sample Output

样例1

3

样例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;
}
1
技术分享 
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define M 100001

using 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;
}
2

例题4：

判决素数个数

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

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

输入
两个整数X和Y（1 <= X,Y <= 105）。
输出
输出一个整数，表示X，Y之间的素数个数（包括X和Y）。
样例输入
1 100
样例输出
25
这道题很坑！有个大坑！

我做了好多遍
给的数据有可能x>y！！！
给的数据有可能x>y！！！
给的数据有可能x>y！！！
技术分享 
#include<iostream>
#include<cstdio>
#include<cmath>
#define M 100001

using 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 100001

using 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;
}
AC
例题5：
codevs 1702 素数判定2
题目描述 Description

一个数，他是素数么？

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

 





输入描述 Input Description




P










输出描述 Output Description




Yes|No










样例输入 Sample Input




2


 










样例输出 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 5005

using 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




6






















样例输出 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：


5
7
11
101
131
151
181
191
313
353
373
383







说明


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
原文：http://www.cnblogs.com/zxqxwnngztxx/p/6735297.html

                

                
                

                    

                        

                            

                                

                                    踩

                                

                                    (0)

                            

                            

                                

                                    赞

                                

                                    (0)

                            

                            

                            

                        

                        

                            

                                    
                                
                            

                        

                    

                    

                        举报
                    

                    
                    

                        

                            评论 一句话评论（0）
                        

                        

                            
                            

                                
                            

                        

                        

                            

                            

                                

                                

                                

                                    
                                

                            

                            
                            

                        

                    

                

                
            

        
        

            

    



            
            


    

        

            分享档案

        

            更多>
        

        

        

    

    

        
                
                    2021年09月23日
                    (328)

            
                
                    2021年09月24日
                    (313)

            
                
                    2021年09月17日
                    (191)

            
                
                    2021年09月15日
                    (369)

            
                
                    2021年09月16日
                    (411)

            
                
                    2021年09月13日
                    (439)

            
                
                    2021年09月11日
                    (398)

            
                
                    2021年09月12日
                    (393)

            
                
                    2021年09月10日
                    (160)

            
                
                    2021年09月08日
                    (222)

            
    




            


    

        
最新文章

        

            更多>

        

        

    

    

        
    




            


    

        
教程昨日排行

        

            更多>

        

        

    

    

        
    




            
        

        

        

    
    
    

    

        

            友情链接
        

        

            汇智网  
            PHP教程  
            插件网  
					
			
        

    





    

        

            

                关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
            

            

                © 2014 bubuko.com 版权所有
            

            

                打开技术之扣，分享程序人生！