问题同上,要求输入一个超过2^16次方的数字,判断是否为素数.要快速出结果.

彪悍的中英结合

你来贴分的吧????????????

我也正在为这个素数问题烦恼呢

根据费马小定理的随机素数判定法

include <stdio.h>
#include <math.h>
int Prime(int x)
{
    int i,tn;
    tn=sqrt(x)+1;
    if(x==1) return(0);
    if(x==2) return(1);
    if(x%2==0)return(0);
    for(i=3;i<=tn;i+=2)
    if(x%i==0)
    return(0);
    return(1);
}
void main()
{
    int a;
    printf("enter one integer:");
    scanf("%d",&a);
    if(Prime(a)) printf("此数为素数");
    else printf("此数不是素数");
}

#include<stdio.h>
#include<math.h>
void main()
{
    int a,n=0;
    printf("请输入一个大于2^16的整数: ");
re:
    scanf("%d",&a);
    if(a<=1024*64)
    {printf("出错!请重新输入: ");goto re;}
    else
    {
        for(int i=2;i<sqrt(a+1);i++)
    {
        if(a%i==0)   {printf("不是素数!因数是: %d\n",i);break;}
        else {n++;continue;}
    }
    if(n==int(sqrt(a+1)-1))
        printf("是素数!\n");

    }
}

我的程序可以快速判断几十位的，原理是利用了RSA密码体制的逆命题，大于5位的都是正确的，因为我的明文是3位的就是123，是用余数来还原的，如果位数低了如小于3位，余数就不可能是3位的原理失效，还原不了。对大素数判断是快的，用到了快速幂模算法，由于我不会大整数的快速乘法除法，对大整数的乘法除法是模仿手工竖式计算的，效率低速度慢，只能判断单个几十位的，100位以上就慢了，需要1小时以上。希望老师给个大整数的快速乘法除法的可调用程序，用VB编程的，我不会VC。会快速乘法除法原理的也欢迎指导讲解！

谢谢您！祝愿老师新年快乐，阖家幸福安康，万事如意！

[此贴子已经被作者于2020-2-10 23:36编辑过]

这种方法是确定性的判断，但不能分解因子，比常规法快，但不会大整数的快速乘除法计算就效率低了，仅能判断几十位的整数。若会了快速乘法除法程序就可以算更大的。

如下数据是用这个程序做的：
1000520000与1000550000之间有100对孪生素数对:
1000520621和 1000520623  孪中1000520622
1000520777和 1000520779  孪中1000520778
1000521029和 1000521031  孪中1000521030
1000521059和 1000521061  孪中1000521060
1000521161和 1000521163  孪中1000521162
1000521629和 1000521631  孪中1000521630
1000521671和 1000521673  孪中1000521672
1000521749和 1000521751  孪中1000521750
1000523429和 1000523431  孪中1000523430
1000524071和 1000524073  孪中1000524072
1000524431和 1000524433  孪中1000524432
1000524521和 1000524523  孪中1000524522
1000524689和 1000524691  孪中1000524690
1000525151和 1000525153  孪中1000525152
1000525637和 1000525639  孪中1000525638
1000525709和 1000525711  孪中1000525710
1000526669和 1000526671  孪中1000526670
1000526981和 1000526983  孪中1000526982
1000527257和 1000527259  孪中1000527258
1000527389和 1000527391  孪中1000527390
1000527431和 1000527433  孪中1000527432
1000527947和 1000527949  孪中1000527948
1000528031和 1000528033  孪中1000528032
1000528259和 1000528261  孪中1000528260
1000528271和 1000528273  孪中1000528272
1000528367和 1000528369  孪中1000528368
1000528511和 1000528513  孪中1000528512
1000529267和 1000529269  孪中1000529268
1000529351和 1000529353  孪中1000529352
1000529357和 1000529359  孪中1000529358
1000530161和 1000530163  孪中1000530162
1000530467和 1000530469  孪中1000530468
1000530647和 1000530649  孪中1000530648
1000530761和 1000530763  孪中1000530762
1000531109和 1000531111  孪中1000531110
1000531247和 1000531249  孪中1000531248
1000531421和 1000531423  孪中1000531422
1000531529和 1000531531  孪中1000531530
1000531667和 1000531669  孪中1000531668
1000531709和 1000531711  孪中1000531710
1000531997和 1000531999  孪中1000531998
1000532051和 1000532053  孪中1000532052
1000532459和 1000532461  孪中1000532460
1000532579和 1000532581  孪中1000532580
1000533641和 1000533643  孪中1000533642
1000533731和 1000533733  孪中1000533732
1000533881和 1000533883  孪中1000533882
1000534121和 1000534123  孪中1000534122
1000534817和 1000534819  孪中1000534818
1000535531和 1000535533  孪中1000535532
1000535771和 1000535773  孪中1000535772
1000536287和 1000536289  孪中1000536288
1000536707和 1000536709  孪中1000536708
1000536839和 1000536841  孪中1000536840
1000537037和 1000537039  孪中1000537038
1000537301和 1000537303  孪中1000537302
1000537451和 1000537453  孪中1000537452
1000537709和 1000537711  孪中1000537710
1000537721和 1000537723  孪中1000537722
1000538447和 1000538449  孪中1000538448
1000538909和 1000538911  孪中1000538910
1000539497和 1000539499  孪中1000539498
1000539611和 1000539613  孪中1000539612
1000539731和 1000539733  孪中1000539732
1000540031和 1000540033  孪中1000540032
1000540061和 1000540063  孪中1000540062
1000540241和 1000540243  孪中1000540242
1000540691和 1000540693  孪中1000540692
1000541021和 1000541023  孪中1000541022
1000541039和 1000541041  孪中1000541040
1000541369和 1000541371  孪中1000541370
1000541741和 1000541743  孪中1000541742
1000541777和 1000541779  孪中1000541778
1000541909和 1000541911  孪中1000541910
1000542581和 1000542583  孪中1000542582
1000542731和 1000542733  孪中1000542732
1000542911和 1000542913  孪中1000542912
1000543799和 1000543801  孪中1000543800
1000544429和 1000544431  孪中1000544430
1000544591和 1000544593  孪中1000544592
1000545449和 1000545451  孪中1000545450
1000545899和 1000545901  孪中1000545900
1000546091和 1000546093  孪中1000546092
1000546187和 1000546189  孪中1000546188
1000546319和 1000546321  孪中1000546320
1000546451和 1000546453  孪中1000546452
1000546751和 1000546753  孪中1000546752
1000546889和 1000546891  孪中1000546890
1000546997和 1000546999  孪中1000546998
1000547369和 1000547371  孪中1000547370
1000547501和 1000547503  孪中1000547502
1000547759和 1000547761  孪中1000547760
1000548161和 1000548163  孪中1000548162
1000548539和 1000548541  孪中1000548540
1000548977和 1000548979  孪中1000548978
1000549157和 1000549159  孪中1000549158
1000549181和 1000549183  孪中1000549182
1000549349和 1000549351  孪中1000549350
1000549439和 1000549441  孪中1000549440
1000549577和 1000549579  孪中1000549578

如下这个素数是这个程序判断出来的：
233333333333333333333333333333333333333333333333333333这是素数有54位