if (j…) printf ("… prime\n"); else printf ("… not prime\n"); Prime Number (質數1) Q: Enter n: 13 Prime Number (質數1) Q: Enter n: 24 A: 13 is prime A: 24 is not prime 沒有一個 j 可以整除 n 至少 有一個 j 可以整除 n n % j 13 % 2 = 1 13 % 3 = 1 13 % 4 = 1 13 % 5 = 3 13 % 6 = 1 … 13%12 = 1 n % j 24 % 2 = 0 24 % 3 = 0 24 % 4 = 0 24 % 5 = 4 24 % 6 = 0 … 24%23 = 1 for (j=2;j<…;j++) if (n…j…) break; if (j…) printf ("… prime\n"); else printf ("… not prime\n"); 質數
Prime Factors (質因數2) Q: Enter n: 70 Prime Factors (質因數2) n % j = r 70 % 2 = 0 35 % 3 = 2 35 % 4 = 3 35 % 5 = 0 7 % 6 = 1 7 % 7 = 0 n % j = r 24 % 2 = 0 12 % 2 = 0 6 % 2 = 0 3 % 3 = 0 scanf("%i", &n); j=2; while (n>?){ if (n%?==0){ printf… n = … }else //試下一個數 } scanf("%i", &n); for (j=2;j<…;j++) if (n%2==0){ printf… n = … } 質數
Prime Number (質數3) Q: Enter max: 100 A: prime numbers are 2,3,5,7,11,13,…,97 for (n=2;n<100;n++){ } n=24; for (j=2;j<√n;j++) if (n%?==0) break; if(j…) printf… 質數
Array Prime Number (質數4) Q: Enter max: 100 A: prime numbers are 2,3,5,7,11,13,…,97 j n%j 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 … n=4 n=5 n=6 n=7 n=8 n=9 : 100 1 1 1 2 2 1 3 2 3 1 4 凡可被 j 整除的都不是質數 質數
for (i=1;i<101;i++) prime[i]=1; 假設全部為 質數(1) Prime Number (質數1-100) int prime[101]={0}; for (i=1;i<101;i++) prime[i]=1; k=2 prime[4] = 0; prime[6] = 0; prime[8] = 0; prime[10] = 0; … prime[100] = 0; k=3 prime[6] = 0; prime[9] = 0; prime[12] = 0; prime[15] = 0; … prime[99] = 0; k=4 prime[8] = 0; prime[12] = 0; prime[16] = 0; prime[20] = 0; … prime[100] = 0; 非質數(0) k=2; for (j=2;j<…;j++) prime[...] = 0; k=3; for (j=2;j<…;j++) prime[...] = 0; printf("100以內的質數: "); for(i=2;i<100;i++) if(prime[i]==1) printf(...); 質數
公因數 HCF/GCD Q: Enter a,b: 18 24 A: common factors are 2,3,6 min = 18 24 A: common factors are 2,3,6 公因數 min = printf ("A: common factors are "); for (j=2; j<min; j++){ if( ){ printf (" %i, ", ); hcf = ; } printf ("\n最大公因數HCF= %i\n", hcf); 質數