[204] Count Primes

雖說也是先看了找質數的演算法的說明才寫的
但速度還是有點快的驚人 囧
是已經太習慣超級慢寫法了嗎 XD
點一, 只要找平方根以內的就好
（為什麼呢～數學真難參透啊）
點二, 先弄一個全部設成true的array
然後從2, 3,.....開始, 將質數的倍數都設成false
最後再找出這個array裡面有幾個true, 也就是有幾個質數
The End.


Count Primes
int countPrimes(int n) {
    if (n<=2)
        return 0;
    bool *isPrime = malloc(sizeof(bool)*(n+1));
    memset(isPrime, true, n);
    isPrime[0] = isPrime[1] = false;
    int i,j;
    for (i=2;i<sqrt(n);i++)
        if(isPrime[i])
            for (j=i*i;j<n;j+=i)
                isPrime[j]=false;
    int count =1;
    for(i=3;i<n;i+=2)
        if (isPrime[i]==true)
            count++;
   return count;
}

20230925 update

時隔多年，寫出了奇怪的東西？！果不其然，忘記可以用 sqrt 來加速了

但好像因為想用count 直接紀錄，而不是最後再去算沒被clear掉的有幾個(等於質數個數）

所以變的怪怪的XD 先降子好了XDDDD(光速逃）

int countPrimes(int n){

if (n==0 || n==1)

return 0;

int *check =calloc (n+1, sizeof(int));

int count=0;

for (int i=2; i<n+1;i++)

{

if (check[i]== 0)

{

if (i==n)

break;

count++;

int j=i;

for (int j=i; j<n+1;j+=i)

check[j]= -1;

}

}

return count;

}