質數定義：
大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個因數的數）。
(取自維基)

  求某數 N 是否為 質數 演算法
基本演算法：
1.測試 1 是否可整除 N? 是的話，計數器+1。
2.測試 2 是否可整除 N? 是的話，計數器+1。
3.重複測試，直到測試 N 是否可整除 N? 是的話，計數器+1。
4.結束以上測試後，判斷計數器的數量(即為N的因數數量)，若為2，
   即表示只有 1 與 N 可整除N，則該數 N 為質數。
   計數器若大於2，就表示除了1 與 N 可整除N以外，尚有其他數可整除N，
   則判定 N 非質數。
  延伸問題：
計算某範圍內的自然數，共有幾個質數。

問題描述：
計算 1 至 y，共有幾個質數。(y為大於1的自然數)

基本演算法：
1.測試 2 至 y 每一位自然數。(排除1的測試)
2.每一個自然數的測試，以上述測試質數的方法測試之。若為質數，則質數數量計數器+1。
3.當2至y的每一個自然數均測試完畢後，質數數量計數器的值即為所求。
  測試問題：
求 1 至 1000000 自然數中，共有幾個質數？

  方法一：
1.設定 y 的範圍 為 2 至 1000000
2.設定 N=y
3.   將整數 N，除以 x (x 範圍為1 至 N)，並統計x可以整除N的數量。
4.   若數量等於2個，則是質數，並計數器+1。
5.當 y 跑完範圍，計數器的數量即為所求。

ss=0;
for(y=2;y<=N;y++)
{
   n=y;
   for(x=1,s=0;x<=n;x++)
      if((n%x)==0)
         s++;
   if(s==2)
      ss++;
}
cout << ss << "個.\n";

  方法二：
1.設定 y 的範圍 為 2 至 1000000
2.設定 N=y
3.      將整數 N，除以 x (x 範圍為2 至 N-1)
4.      當x 可以整除 n，則離開迴圈。
5.若不是因為x 可以整除 n 而離開迴圈的話，質數數量+1。
6.當 y 跑完範圍，計數器的數量即為所求。

ss=0;
for(y=2;y<=N;y++)
{
   n=y;
   for(x=2;x<n;x++)
      if((n%x)==0)
         break;
   if(x==n)
      ss++;
}
cout << ss << "個.\n";

  方法三：
1.設定 y 的範圍 為 2 至 1000000
2.設定 N=y
3.   將整數 N，除以 x (x 範圍為2 至 √N )
4.   當x 可以整除 n，則離開迴圈。
5.若不是因為x 可以整除 n 而離開迴圈的話，質數數量+1。
6.當 y 跑完範圍，計數器的數量即為所求。
ss=0;
for(y=2;y<=N;y++)
{
   n=sqrt(y);
   for(x=2;x<=n;x++)
      if((y%x)==0)
         break;
   if(x==n+1)
      ss++;
}
cout << ss << "個.\n";

  方法四：
1.設定 y 的範圍 為 3 至 1000000 (y 以奇數的方式運算)
2.設定質數數量=1 (2算1個質數)
3.設定 N=y
4.   將整數 N，除以 x (x 範圍為3 至 √N , x 以奇數的方式運算)
5.   當x 可以整除 n，則離開迴圈。
6.若不是因為x 可以整除 n 而離開迴圈的話，質數數量+1。
7.當 y 跑完範圍，計數器的數量即為所求。

ss=1;
for(y=3;y<=N;y+=2)
{
   n=sqrt(y);
   for(x=3;x<=n;x+=2)
      if((y%x)==0)
         break;
   if(x>=n+1)
   ss++;
}
cout << ss << "個.\n";
  方法五：
1.使用陣列紀錄質數的倍數。(因為質數的倍數，不是質數)
2.設定 y 的範圍 為 3 至 1000000 (y 以奇數的方式運算)
3.設定質數數量=1 (2算1個質數)
4.求證 陣列是否被記錄
5.   是的話表示非質數
6.   不是的話，就表示質數，質數數量+1，並做下列運算。
7.陣列紀錄該質數的倍數。
8.當 y 跑完範圍，計數器的數量即為所求。

char t[N];
for(x=3;x<=N;x+=2)
   t[x]='\0'; ss=1;
for(y=3;y<=N;y+=2)
{
   if(t[y]=='\0')
   {
      ss++;
      for(x=y;x<=N;x+=y)
         t[x]='\1';
   }
}
cout << ss << "個.\n";
 
 使用時間使用記憶體
方法一
1541.89
 16
方法二
126 . 756
 16
方法三
0 . 236
 16
方法四
0 . 123
 16
方法五
0 . 016
 1000012
  教學影片