NYOJ 225题小明求素数积

2024-06-11 15:58

文章标签 225 素数 nyoj 小明求

本文主要是介绍NYOJ 225题小明求素数积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

应用到的知识点：

1.筛选素数（见素数）；

2.大数乘法（见求高精度幂）；

要注意的是：后六位不能以0开头！

    
#include<stdio.h> 
#include<string.h> 
intmain()  
{ 
    booln[1000] = {0};//标记所有的素数；  
    inti, j;  
    for(i = 2; i * i <= 1000; i ++)  
    { 
        if(n[i] == 0)  
        for(j = i + i; j <= 1000; j += i )  
        { 
            n[j] = 1; 
        } 
    } 
    intT;  
    scanf("%d", &T);  
    while(T --) 
    { 
        intN;  
        scanf("%d", &N);  
        intinput[2000] = {0}, temp[2000] = {0}, output[2000] = {2};  
        intnum,   out = 1, k = 0, m = 0;//in，input中元素个数；out，output中元素的个数； 
        for(i = 3; i <= N; i ++)//模拟手算；  
        { 
            intj = 0,in = 0;  
            if(n[i] == 0)//针对所有素数；  
            { 
                num = i; 
                while(num != 0)  
                { 
                    input[j ++] = num % 10; 
                    num /= 10; 
                    in ++; 
                }//将素数一位一位地，倒序地，存到input数组里面； 
                for(j = 0; j < in; j ++)  
                { 
                    intl = j, s[2000] = {0}, c[2000] = {0};  
                    for(k = 0; k < out; k ++)  
                    { 
                        s[l] = (c[l] + input[j] * output[k]) % 10;    
                        c[l +1] = (c[l] + input[j] * output[k]) / 10;     
                        temp[l] += s[l];     
                        l ++; 
                    } 
                    if(c[l] != 0)  
                    { 
                        temp[l] = c[l]; 
                        l = l + 1; 
                    } 
                    m = l; 
                } 
                out = m; 
                inttempc[2000] = {0};  
                for(m = 0; m < out; m ++)  
                { 
                    output[m] = (temp[m] + tempc[m]) % 10;    
                    tempc[m +1] = (temp[m] + tempc[m]) / 10;      
                } 
                if(tempc[m] != 0)  
                { 
                    output[m] = tempc[m]; 
                    out = out + 1; 
                } 
                memset(temp, 0, sizeof(temp));//将temp清零； 
            } 
        } 
        if(out <= 6)//总位数<=6, >6, 倒序输出；输出时，竟然还不能以零开头！！！  
        { 
            for(i = out - 1; i >= 0; i --)  
                printf("%d", output[i]);  
        } 
        else 
        { 
            for(i = 5; i >= 0; i --)  
            { 
                 if(output[i] != 0)  
                     break; 
            } 
            for(j = i; j >= 0; j --)  
                printf("%d", output[j]);  
        } 
        printf("\n"); 
    } 
    return0;  
} 