【求助】有关于最大公约数的一个问题！
有一道题是求：
一个整数N，找出所有小于它的正整数的个数，并且这个正整数与它的最大公约数为1.
样例：
对于25608有7680个符合这个条件的正整数。
我的思路：
从1开始，找出与它的最大公约数大于1的一个数，比如说2，然后将2,4,6,8……（2*n<N)记录下来，然后后面的这些就不用找了，最后知道所有的都找完。这个算法的时间太长了，勉强过了。希望哪位大神给出耗时很少的算法！
[解决办法]
按你的思路筛选法，x=1000000，耗时0.2s，我是x64的，x86的请将ulong64改成uint
#include <stdio.h>#include <Windows.h>inline BOOLEAN IsEven(ULONG64 x){ if (x & 0x01ULL) return FALSE; else return TRUE;}ULONG64 GCD(ULONG64 x, ULONG64 y){ if (x < y) return GCD(y, x); if (y == 0) return x; else { if (IsEven(x)) { if (IsEven(y)) return GCD(x>>1, y>>1) << 1; else return GCD(x>>1, y); } else { if (IsEven(y)) return GCD(x, y>>1); else return GCD(y, x-y); } }}void TimeStart(LARGE_INTEGER *pBegintime){ QueryPerformanceCounter(pBegintime);}LPSTR TimeResult(LARGE_INTEGER *pBegintime, LPSTR szTime){ LARGE_INTEGER endtime; LARGE_INTEGER freqtime; LARGE_INTEGER resulttime; QueryPerformanceCounter(&endtime); QueryPerformanceFrequency(&freqtime); resulttime.QuadPart = (endtime.QuadPart - pBegintime->QuadPart) * 1000 / freqtime.QuadPart; sprintf(szTime, "%I64d小时%I64d分%I64d.%03I64d秒", resulttime.QuadPart / 3600000, (resulttime.QuadPart / 60000) % 60, (resulttime.QuadPart /1000) % 60, resulttime.QuadPart % 1000); return szTime;}int main(){ const int x = 2560800; int i = 0, count = 0, j = 0, n = 0; unsigned char *tab = (unsigned char*)malloc(x); memset(tab, 0x00, x); LARGE_INTEGER b, f, e, r; QueryPerformanceCounter(&b); for (i=1; i<x; ++i) { if (tab[i]) continue; if (GCD(x, i) == 1) count++; else { for (j=0, n=0; n<x; ++j) { n = i * j; if (n<x) tab[n] = 1; } } } QueryPerformanceFrequency(&f); QueryPerformanceCounter(&e); r.QuadPart = (e.QuadPart - b.QuadPart) * 1000 / f.QuadPart; printf("%d\n", count); printf("%lld小时%lld分%lld.%03lld秒\n", r.QuadPart / 3600000, (r.QuadPart / 60000) % 60, (r.QuadPart /1000) % 60, r.QuadPart % 1000); free(tab); getchar();}