素数求和
嘿嘿,这个暑假我要多多刷题。原题地址: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;
for (int i=0;i<n;i++)
{
int n2;
int Nums;
int sum1=0;
scanf("%d",&n2);
for (int j=0;j<n2;j++)
{
scanf("%d",&Nums);
if (isPrime(Nums))
sum1+=Nums;
}
reason = sum1;
}
for (int i=0;i<n;i++)
printf("%d\n",reason);
return 0;
} ←_← 你这样效率太低了点吧 首先比如取余 是16 你到 根号16 就好了 大于死的根本不用试了 其次 比如 4 可以 2肯定行 也就是说已知的和数也不需要 简单点的思路 先2 看是不是和数 是就不管 不是就从3开始每次2+就好这样至少不会是偶数
当然你还可以没求出一个素数就放到数组里下次就直接用数组里的素数来取余就好 这样效率会高好多
当然还有筛法等等 ~~~你这个效率真心低
页:
[1]