主題：質(zhì)數(shù)與其應(yīng)用-資料下載頁
2025-09-19 02:26本頁面
【導(dǎo)讀】一個(gè)大於等於2的數(shù)，除了1及本身，1是不是質(zhì)數(shù)依題目規(guī)定。只要2到n-1間的整數(shù)都不是n的因數(shù)，假設(shè)已建好一範(fàn)圍在2到n-1(n?prime[i]代表第i+1個(gè)質(zhì)數(shù)。只要比sqrt小的所有質(zhì)數(shù)都不是n的。假設(shè)我們要求出在1~range的範(fàn)圍內(nèi)所。利用判斷質(zhì)數(shù)的方法造表。1的數(shù)字才需要測(cè)試，其他都。不使用除法的建表法。對(duì)於每個(gè)質(zhì)數(shù)來說，它的倍數(shù)一定不是質(zhì)數(shù)，建立一個(gè)listarray代表質(zhì)因數(shù)列表。建立一個(gè)counterarray來代表每個(gè)質(zhì)。以為例，直接將分母分子算出，再做。Goldbach假說:所有的偶數(shù)都是兩個(gè)質(zhì)數(shù)。給一個(gè)偶數(shù)n，找四個(gè)質(zhì)數(shù)p1，p2，p3，p4，有一數(shù)除以3餘2，除以5餘3，除以7. 進(jìn)階中國餘式定理
【正文】 ? int is_prime [range] ? 篩法建立的質(zhì)數(shù)表 ? int num_pfact ? num 的質(zhì)因數(shù)個(gè)數(shù) ? int ppow[range] ? num 因數(shù)分解後，每個(gè)質(zhì)因數(shù)的次方數(shù) 25 解法 ? 建質(zhì)數(shù)表 ? 質(zhì)因數(shù)分解 ? 決定最大次方數(shù) ? 考慮 num 是負(fù)數(shù)的狀況 26 Program structure construct_is_prime()。 //建質(zhì)數(shù)表 while(1) { scanf(“%d”, amp。num)。 if(num == 0) break。 // input 結(jié)束 flag = 0。 // 假設(shè) num 為正 if(num 0) flag = 1。 // num 為負(fù)，改變 flag factorial(num)。 //因數(shù)分解，只需記次方數(shù) find_max_power()。 if(flag == 1) num_is_minus()。 output()。 } // end of while 27 決定最大次方數(shù) ? 如何決定最大次方數(shù) ? ? n = 129600 = 26 ? 34 ? 52 = (23 ? 32 ? 5)2 ? n 的次方數(shù)必是質(zhì)因數(shù)次方數(shù)的公因數(shù) ? 最大次方數(shù)為所有的質(zhì)因數(shù)次方數(shù)求 最大公因數(shù) 28 求公因數(shù) ? a, b 兩數(shù)求公因數(shù) ? 輾轉(zhuǎn)相除法 int gcd(int a, int b) { int c。 if(a b) swap(a, b)。 //讓 a b if(a%b != 0) return gcd(b, a%b)。 else return b。 } 29 若 num 是負(fù)的 ? 只有奇數(shù)次方才有可能為負(fù)數(shù) ? 將之前求得的次方數(shù)不斷除以二，直到成為奇數(shù)為止 30 歷年題目 ? 練習(xí)題 ? Summation of Four Primes ? ? Perfect Pth Powers ? ? Prime Distance ? ? 挑戰(zhàn)題 ? Goldbach and Euler ? ? 其他歷年題目 ? 無
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1