試撰寫一程式，由鍵盤輸入一個整數，然後判別此數是否為質數(prime)。
若是，則印出"此數是質數"字串，若不是，則印出"此數不是質數"字串。
(質數是指除了1和它本身之外，沒有其他的數可以整除它的數，例如，2,3,5,7與11等皆為質數)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| int is_prime(int); | |
| int main(int argc, char *argv[]) | |
| { | |
| int number; | |
| scanf("%d",&number); | |
| if(is_prime(number)){ | |
| printf("此數是質數\n"); | |
| }else{ | |
| printf("此數不是質數\n"); | |
| } | |
| system("PAUSE"); | |
| return 0; | |
| } | |
| int is_prime(int num){ | |
| int i; | |
| if(num==1){ | |
| return 0; | |
| }else{ | |
| for(i=2;i<num;i++){ | |
| if(num%i==0){ | |
| return 0; | |
| } | |
| } | |
| } | |
| return 1; | |
| } |
上述做法時間複雜度為O(n)
若改用以下做法，時間複雜度為O(n^1/2)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<stdio.h> | |
| int isPrime(int n); | |
| int main() | |
| { | |
| int n; | |
| scanf("%d", &n); | |
| if(isPrime(n)) | |
| { | |
| printf("It's a prime\n"); | |
| }else{ | |
| printf("It's not a prime\n"); | |
| } | |
| return 0; | |
| } | |
| int isPrime(int n) | |
| { | |
| if(n==1) | |
| return 0; | |
| int i=2; | |
| for(; i*i<=n; i++) | |
| { | |
| if(n%i==0) | |
| { | |
| return 0; | |
| } | |
| } | |
| return 1; | |
| } |
判斷質數的方法，就是要找因數，對吧><
但是第一個做法是找出所有的因數
而我們不需要找所有的因數，只需要找一半的因數就行了
例如: 16的因數:1, 2, 4, 8, 16
i=4的時候，i*i=4*4<=16，迴圈就結束了
那8耶~~~~XD
因為判斷質數，如果16能被2整除，那表示也能被8整除，因為2*8=16
所以....
也就說...
跟剛才講的一樣
就是...
只需要找一半的因數就行了
=====================================================================
試撰寫一程式，可由鍵盤讀入一個正整數，並找出小於此數的最大質數。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| #include <stdlib.h> | |
| int is_prime(int); | |
| int main(int argc, char *argv[]) | |
| { | |
| int number,i,Max_prime=0; | |
| scanf("%d",&number); | |
| for(i=1;i<number;i++){ | |
| if(is_prime(i)){ | |
| Max_prime=i; | |
| } | |
| } | |
| printf("小於%d的最大質數為:%d\n",number,Max_prime); | |
| system("PAUSE"); | |
| return 0; | |
| } | |
| int is_prime(int num){ | |
| int i; | |
| if(num==1){ | |
| return 0; | |
| }else{ | |
| for(i=2;i<num;i++){ | |
| if(num%i==0){ | |
| return 0; | |
| } | |
| } | |
| } | |
| return 1; | |
| } |
文章標籤
全站熱搜
留言列表
