鱼C论坛

 找回密码
 立即注册
查看: 3094|回复: 7

[技术交流] 素数求和

[复制链接]
发表于 2015-7-8 22:17:51 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
嘿嘿,这个暑假我要多多刷题。
原题地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=22
难点:判断一个数时候为素数。
质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除,换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。

这里用循环取余的方法。
bool isPrime(int x)
{
        if (x<=1) return false;
        for(int i=2;i<x;i++)
                if (x%i==0)
                        return false;
        return true;
}

完整代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
bool isPrime(int x)
{
        if (x<=1) return false;
        for(int i=2;i<x;i++)
                if (x%i==0)
                        return false;
        return true;
}
char *mystrlen(char *s)
{
        int x=0;
        while (*s!=' ')
        {
                if(*s=='\0') return s;
                x++;
                s++;
        }
        return (char *)(unsigned int)s+(unsigned int)x;
}
int main()
{
        int n;
        int *reason;
        scanf("%d",&n);
        reason = new int[n];
        for (int i=0;i<n;i++)
        {
                int n2;
                int Nums[10000];
                int sum1=0;
                scanf("%d",&n2);
                for (int j=0;j<n2;j++)
                {
                        scanf("%d",&Nums[j]);
                        if (isPrime(Nums[j]))
                                sum1+=Nums[j];
                }
                reason[i] = sum1;
        }
        for (int i=0;i<n;i++)
                printf("%d\n",reason[i]);
        return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-7-11 07:57:31 | 显示全部楼层
←_← 你这样效率太低了点吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 07:58:34 | 显示全部楼层
首先比如取余 是16 你到 根号16 就好了 大于死的根本不用试了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 07:58:52 | 显示全部楼层
其次 比如 4 可以 2肯定行
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 07:59:17 | 显示全部楼层
也就是说已知的和数也不需要
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 08:00:10 | 显示全部楼层
简单点的思路 先2 看是不是和数 是就不管
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 08:01:33 | 显示全部楼层
不是就从3开始每次2+就好这样至少不会是偶数
当然你还可以没求出一个素数就放到数组里下次就直接用数组里的素数来取余就好
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-11 08:02:03 | 显示全部楼层
这样效率会高好多
当然还有筛法等等 ~~~  你这个效率真心低
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 12:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表