求小于1000且与1000互质的所有自然数的和
怎么做?用什么算法呢？

你把1000以内的所有质数找出来，加起来。
找一个加一个找一个加一个就行了。

求质数的算法你应该知道吧。

我知道用C语言可以算出来
但我不会
请达人请教

for (i=1;i<1000,i++){
for(j=1;j=<(i+1)/2;j++){
  if(i%j==0){break;}
  }
if (j>(i+1)){
  sum=i+sum /* i就是质数
}

}

1.上面的算法很形象，最易理解当然计算复杂度是最大的……

2.所有回帖的同学，*质数*和*与1000互质*是一个概念吗？

3.我想不到什么巧方法，笨办法是分解1000的因子，然后从和里减去可能的因子组合。

LS 的说得对 我去看了下 互质数 在小学书上的定义是：两个数只有1这个公约数就互质
看来我应该把数学从小学开始重新学过

#include<iostream.h>
#include<math.h>
void main()
{
int i,k,j;
for(i=3;i<1000;i=i+2)
  {
    k=(int)sqrt(i);
    for(j=2;j<=k;j++)
      if(i%j==0) break;
       if(j>=k+1&&i%5!=0)   //求出1000以内的所有素数，再把５排除
        cout<<i<<' ';
   }
   cout<<endl;
}
哪位ＧＧ有更好的算法分享一下？

Quote:

引用第7楼yyld于2006-10-14 22:16发表的:
#include<iostream.h>
#include<math.h>
void main()
{
int i,k,j;
.......

这位蝈蝈的算法应该不错了

#include <iostream.h>
#include <math.h>

void main()
{
   int i,j,k=0,sum,a[500];
   for(i=2;i<=500;i++)     //求出1000的因子
   {
       if(1000%i==0)
       {
           a[k]=i;
           k++;
       }
   }

   for(i=1;i<1000;i++)     //找出和1000没有公因子的数字
   {
       for(j=0;j<=k;j++)
       {
           if(i%a[j]==0) break;
       }
       if(j=k+1) sum+=i;
   }

   cout<<sum<<endl;
}

shit


貌似flowput了

9楼的算法从数学上来讲,更好.

有一个简单的方法

step 1: 1+2+3+``````+1000=s
step 2: 找出1000以内是2和5的倍数的数,求和u
step3:s-u即为所求
如果我没猜错的话,答案应该是200500