求1到40000的互质数个数！求指导。

筛选法

#include <stdio.h>

bool foot[40005] = {0};
int main()
{
    int i,j,k = 0;
    for(i = 2;i<=200;i++)
    {
        if(!foot[i])
        {
            for(j = 2*i;j<=40000;j+=i)
                foot[j] = 1;
        }
    }
    for(i = 2;i<=40000;i++)
        if(!foot[i])
        {
            k++;
            printf("%d\n",i);
        }
    printf("%d\n",k);
    return 0;
}

题目来源 ：http://www.

亲，我问的是互质数，公因数只有1的两个数，叫做互质数。

请问此题时限是多少？

 /* Note:Your choice is C IDE */
//欧几里得的辗转相除法   基本思路!
#include "stdio.h"
int main()
{
long int x,y,z;
     puts("pleas input two number.");
     scanf( "%d%d" ,&x , &y);
     z = x % y;
     while(z != 0)
     {
         //变换变量的值
         x=y;
         y=z;
         z=x % y;
   
     }
     if(y==1)printf("this two number is prime number!");
     else printf("this two number is not prime number!\nhave greatest common divisor is:%d",y);
     return 0;
}









/* Note:Your choice is C IDE */
//欧几里得的辗转相除法   具体解法!
#include "stdio.h"
int main()
{
long int x,X1,y,Y1,z;
  puts("prime number list:");
  for(X1=1;X1<=4000;X1++)          //4000的只有点大,要计算很一会了
  for(Y1=1;Y1<=4000;Y1++)
  { 
       x=X1;
       y=Y1;
     z = x % y;
     while(z != 0)
     {
         //变换变量的值
         x=y;
         y=z;
         z=x % y;
    
     }
     if(y==1)
     {printf("%4d %4d\t",X1,Y1);}
  }
     return 0;
}

我该怎么说你呢.首先人家的数据量是40000不是4000，所以用这个都能想出的方法肯定不行的，这个方法4000的数据量都要算很久，40000的计算量是4000的一百倍以上

看错了 不过有解法就是好的 说不定过几年,计算机的速度比现在更快,那么这点计算就行了. 这是通法啊.又不是简单的算法就是好算法啊.

怎么说呢，我们为什么研究算法，就是因为计算机运算速度跟不上，我举个例子，就是求n!有多少位，一般第一反应就是先用高精度算出n!，然后统计有多少位，当n达到几十万几百万的时候计算量你可以自己试试，如果换个思路，从数学上考虑位数=lg(n!)+1=lg(1)+lg(2)+...lg(n)+1，很快就可以算出来，这就是算法的作用，说实话，大学学的那些语法什么东西给个完全不会c语言的最多两个星期就可以让他完全掌握，真正目的还是在于学习一些算法，这道题目这种最简单的算法对方既然提问就肯定不会没想到，还是想想别的方法吧

这..想了我一整天了，怎么忘了欧拉公式......

分解质因数复杂度是sqrt(n),然后代入欧拉公式中，总得时间复杂度是n^(3/2),大概可以处理到n=20W左右的数据应该都可以1s内出解

[ 本帖最后由 czz5242199 于 2011-11-21 17:50 编辑 ]