583 - Prime Factors583個主要因素ppt課件

1、583 - Prime Factors99703032 資科二 陳宣耀99703034 資科二 鍾佳樺99703045 資科二 陳乃藩Outline Primality Test Prime Table Prime FactorsPrimality Testint isPrime_s1a(int n) int m; if(n=1) return 0; for(m=2;m 2s for multi-input in one of OJs. How to modify?Primality Testevery even number except 2 is not a prime number.in

2、t isPrime_s1b(int n) int m; if(n=2) return 1; if(n=1)|(n%2=0) return 0; for(m=3;m 2s for multi-input in the same OJ. How to modify?Primality Test Theorem: if x mod n 0 for all 2 x , then n is a prime number. Because that there exist no prime number of n which is larger then .nnPrimality Testint isPr

3、ime_s1c(int n) int m,sqrt_n=sqrt(n); if(n=2) return 1; if(n=1)|(n%2=0) return 0; for(m=3;m=sqrt_n;m+=2) if(n%m=0) return 0; return 1;Primality Test Time complexity = ( ) Running time 0.20s for multi-input in the OJ. Advantage: a fast solution for one input. Any other solution?nPrime Table Eratosthen

4、es: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 2 1 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 3 1 2 3 5 7 11 13 17 19 23 25 29 31 5 1 2 3 5 7 11 13 17 19 23 29 31 . . .Prime Table Eratosthenes: void eratosthenes(int sieve,int size) int i,j,sqrt_size=sqrt(size

5、); sieve0=sieve1=0; for(i=2;isize;+i) sievei=1; for(i=2;i=sqrt_size;+i) if(sievei=1) for(j=i*i;jsize;j+=i) sievej=0; Prime Table Build a prime table from the sieve: int table(int prime, const int sieve, int sizeOfSieve) int i,j=0; for(i=0;isizeOfSieve;+i) if(sievei=1) primej+=i; return j; Prime Tabl

6、e Time complexity = O( n log(log n) ) n is the size of sieve. Usage: Primality Test FactorizationPrime Table Use prime table for Primality Test: int isPrime_s2a(int n,int prime) int i,sqrt_n=sqrt(n); if(n=1) return 0; for(i=0;primei1 is said to be prime if and only if its only positive divisors are

7、itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e., is unique if we assert that fi 1 for all i and for ij.One interesting class of prime numbers are the

8、 so-called Mersenne primes which are of the form 2p- 1. Euler proved that 231 - 1 is prime in 1772 - all without the aid of a computer.Prime FactorsInputThe input will consist of a sequence of numbers. Each line of input will contain one number g in the range -231 g 231, but different of -1 and 1. T

9、he end of input will be indicated by an input line having a value of zero.OutputFor each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number , where each fi is a prime number greater than unity (with for ij), the format

10、of the output line should beWhen g 0, if , the format of the output line should bePrime FactorsSample Input-190-191-192-193-1941951961971981992000Sample Output-190 = -1 x 2 x 5 x 19-191 = -1 x 191-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3-193 = -1 x 193-194 = -1 x 2 x 97195 = 3 x 5 x 13196 = 2 x 2 x 7 x

11、7197 = 197198 = 2 x 3 x 3 x 11199 = 199200 = 2 x 2 x 2 x 5 x 5Prime Factors#include#includeint buildTable(int prime,int sizeOfSieve);int factor(int num,int output,const int table,int sizeOfPrime);int main(void) const int sizeOfArray=sqrt(pow(2,31)-1); int primesizeOfArray,sizeOfPrime; int outputsize

12、OfArray,sizeOfOutput; int input,i; sizeOfPrime=buildTable(prime,sizeOfArray); while(scanf(%d,&input)=1) if(input=0) break; sizeOfOutput=factor(input,output,prime,sizeOfPrime); printf(%d = %d,input,output0); for(i=1;isizeOfOutput;+i) printf( x %d,outputi); printf(n); return 0;/*continue*/Prime Fa

13、ctorsvoid sieveOfEratosthenes(int sieve,int size) int i,j,sqrt_size=sqrt(size); sieve0=sieve1=0; for(i=2;isize;+i) sievei=1; for(i=2;i=sqrt_size;+i) if(sievei=1) for(j=i*i;jsize;j+=i) sievej=0;int buildTable(int prime,int sizeOfSieve) int i,j=0; sieveOfEratosthenes(prime,sizeOfSieve); for(i=0;isizeOfSieve;+i) if(primei=1) primej+=i; return j;/*continue*/Prime Factorsint factor(int num,int output,const int table,int sizeOfPrime) int i,sqrt_num,sizeOfOutput=0; if(num0) outputsizeOfOutput+=-1; num*=-1; else if(num=1) output0=1; ret