| getter |
2007-11-05 09:11 AM |
運算加速
如過運算上要更快的話...
1.除了原來的只有自己能整除自己外。
2.將偶數過濾掉，只保留公因數 2(偶數部分只有 2 是質數)。
3.整除時，把除數的偶數過濾掉。
最簡單的的改良
語法:
//質數計算
#include <stdio.h> //載入函式庫 stdio
#include <stdlib.h> //載入函式庫 stdlib
#define clrscr() system("CLS") //畫面清除巨集
#define pause() puts("\n") & system("PAUSE") //畫面暫停巨集
#define Max 60 //定義最大值常數 = 60
int main()
{
int i,j,mod_counter; //for_loop 變數 i,j；整除統計 mod_counter
clrscr(); //畫面清除
for ( i=2; i<=Max; i++ ) { //取餘數除法的Loop1，i 為被除數
if ( i%2==0 ) { //過濾偶數
if ( i == 2 ) //將公因數 2 保留
printf ("%3d,\t",i);
continue; //略過此次回圈運算
}
mod_counter = 0; //整除統計歸零
for ( j=3; j<=i; j+=2 ) { //取餘數除法的Loop2，j 為除數(奇數運算)
if ( i%j == 0 ) mod_counter ++ ; //當被整除時，整除計數 +1
}
if ( mod_counter == 1 ) printf ("%3d,\t",i);
//當被整除次數只有 1 次，為質數並顯示
}
pause(); //畫面暫停
}
位元輸入改
語法:
//質數計算
#include <stdio.h> //載入函式庫 stdio
#include <stdlib.h> //載入函式庫 stdlib
#include <math.h> //載入函式庫 math
#define clrscr() system("CLS") //畫面清除巨集
#define pause() puts("\n") & system("PAUSE") //畫面暫停巨集
main()
{
unsigned long int i,j,mod_counter; //for_loop 變數 i,j；整除統計 mod_counter
unsigned long int min=0,max=0,counter = 0;
int inupt_exp;
clrscr(); //畫面清除
printf ("\n請輸入欲求取質數的位元數：");
scanf("%d",&inupt_exp);
clrscr(); //畫面清除
printf ("\n %d 位元質數：\n",inupt_exp);
printf ("\n最小質數");
for ( i=1; i<=pow(2,inupt_exp)-1; i++ ) { //取餘數除法的Loop1，i 為被除數
if ( i%2==0 ) { //過濾偶數
if ( i == 2 ) { //將公因數 2 保留
counter ++; //統計質數的個數
min = i; //紀錄最小的質數
printf ("為 %d\n",i);
}
continue; //略過此次回圈運算
}
mod_counter = 0; //整除統計歸零
for ( j=3; j<=i; j+=2 ) //取餘數除法的Loop2，j 為除數(奇數運算)
if ( i%j == 0 ) mod_counter ++ ; //當被整除時，整除計數 +1
if ( mod_counter == 1 ) { //當被整除次數只有 1 次，並輸出最大質數
counter ++; //統計質數的個數
max = i; //紀錄最大的質數
}
}
if ( min == 0) printf (" 沒有\n");
printf ("\n最大質數");
if ( max > 0) printf ("為 %d\n",max); else printf (" 沒有\n");
printf ("\n共有 %d 個值數\n",counter);
pause(); //畫面暫停
}
範圍輸入改
語法:
//質數計算
#include <stdio.h> //載入函式庫 stdio
#include <stdlib.h> //載入函式庫 stdlib
#include <math.h> //載入函式庫 math
#define clrscr() system("CLS") //畫面清除巨集
#define pause() puts("\n") & system("PAUSE") //畫面暫停巨集
#define swap(x,y) (x^=y^=x^=y) //數值交換巨集
main()
{
unsigned long int i,j,mod_counter; //for_loop 變數 i,j；整除統計 mod_counter
unsigned long int min=0,max=0,counter=0;
unsigned long int inupt_A,inupt_B;
clrscr(); //畫面清除
printf ("\n請輸入欲求取質數的數值 A ：");
scanf("%d",&inupt_A);
printf ("\n請輸入欲求取質數的數值 B ：");
scanf("%d",&inupt_B);
clrscr(); //畫面清除
printf ("\n%d ~ %d 的質數：\n",inupt_A,inupt_B);
printf ("\n最小質數");
if (inupt_A > inupt_B) //A值 > B值，就互換數值
swap(inupt_A,inupt_B);
for ( i=inupt_A; i<=inupt_B; i++ ) { //取餘數除法的Loop1，i 為被除數
if ( i%2==0 ) { //過濾偶數
if ( i == 2 ) { //將公因數 2 保留
counter ++; //統計質數的個數
min = i; //紀錄最小的質數
max = i; //紀錄最大的質數
printf ("為 %d\n",i);
}
continue; //略過此次回圈運算
}
mod_counter = 0; //整除統計歸零
for ( j=3; j<=i; j+=2 ) //取餘數除法的Loop2，j 為除數(奇數運算)
if ( i%j == 0 ) mod_counter ++ ; //當被整除時，整除計數 +1
if ( mod_counter == 1 ) { //當被整除次數只有 1 次，並輸出最大質數
counter ++; //統計質數的個數
if ( counter == 1 ) {
min = i; //紀錄最小的質數
printf ("為 %d\n",i);
}
max = i; //紀錄最大的質數
}
}
if ( min == 0) printf (" 沒有\n");
printf ("\n最大質數");
if ( min > 0) printf ("為 %d\n",max); else printf (" 沒有\n");
printf ("\n\n共有 %d 個值數\n",counter);
pause(); //畫面暫停
}
|
