題目：

2520是最小的能被1-10中每個(gè)數(shù)字整除的正整數(shù)。

最小的能被1-20中每個(gè)數(shù)整除的正整數(shù)是多少？

分析：

解題方法

題目的實(shí)質(zhì)是求幾個(gè)數(shù)的最小公倍數(shù)。

任何一個(gè)正整數(shù)都可以表示成幾個(gè)素?cái)?shù)的次方的乘積

假設(shè)PnPn表示第n個(gè)素?cái)?shù)，那么任意正整數(shù)可以通過下面的式子獲得：

Num=Pk11Pk22Pk33?Pknn,n∈N+，kn∈NNum=P1k1P2k2P3k3?Pnkn,n∈N+，kn∈N

?

一個(gè)整數(shù)要能被1-10的所有整數(shù)整除，那么就等同于他能被1-10之間的所有素?cái)?shù)整除。那么此時(shí)：

2520=2k1×3k2×5k3×7k42520=2k1×3k2×5k3×7k4

KnKn的取值要保證最終值可以被所有含PnPn約數(shù)的數(shù)整除。以P1=2P1=2舉例，注意到8是含有約數(shù)2的最大整數(shù)，所以K1=3K1=3。同理求得其它的k值。最終得到以下式子：

2520=23×32×5×72520=23×32×5×7

那么對于能被1-20的所以整數(shù)整除的數(shù)，它可以表示成如下形式：

Num=2k1×3k2×5k3×7k4×11k5×13k6×17k7×19k8Num=2k1×3k2×5k3×7k4×11k5×13k6×17k7×19k8

最終求得：

232792560=24×32×5×7×11×13×17×19 那么這些素?cái)?shù)的次方怎么求呢？以2為例子，我們先假設(shè)pow(2,x)=20,兩邊同時(shí)乘于log10,則x=log10(20)/log10(2); #include<stdio.h> #include<math.h> int POW(int a,int b) {int ans=1;for(int i=1 ; i<=b ; i++)ans=a*ans;return ans; } int main( ) {int p[10]={0,2,3,5,7,11,13,17,19};int a[30];int k=20;int N=1;int i=1;bool op=true;int li=sqrt(k);while(p[i]<=k){a[i]=1;if(p[i]<=li){a[i]=floor(log(k)/log(p[i]));}i = i+1;}for(int i=1 ; i<=8 ; i++){N=N*POW(p[i],a[i]);}printf("%d\n",N);} View Code

?

解題方法

題目的實(shí)質(zhì)是求幾個(gè)數(shù)的最小公倍數(shù)。

任何一個(gè)正整數(shù)都可以表示成幾個(gè)素?cái)?shù)的次方的乘積

假設(shè)PnPn表示第n個(gè)素?cái)?shù)，那么任意正整數(shù)可以通過下面的式子獲得：

Num=Pk11Pk22Pk33?Pknn,n∈N+，kn∈NNum=P1k1P2k2P3k3?Pnkn,n∈N+，kn∈N

?

一個(gè)整數(shù)要能被1-10的所有整數(shù)整除，那么就等同于他能被1-10之間的所有素?cái)?shù)整除。那么此時(shí)：

2520=2k1×3k2×5k3×7k42520=2k1×3k2×5k3×7k4

KnKn的取值要保證最終值可以被所有含PnPn約數(shù)的數(shù)整除。以P1=2P1=2舉例，注意到8是含有約數(shù)2的最大整數(shù)，所以K1=3K1=3。同理求得其它的k值。最終得到以下式子：

2520=23×32×5×72520=23×32×5×7

那么對于能被1-20的所以整數(shù)整除的數(shù)，它可以表示成如下形式：

Num=2k1×3k2×5k3×7k4×11k5×13k6×17k7×19k8Num=2k1×3k2×5k3×7k4×11k5×13k6×17k7×19k8

最終求得：

232792560=24×32×5×7×11×13×17×19

轉(zhuǎn)載于:https://www.cnblogs.com/shuaihui520/p/9048145.html

總結(jié)

以上是生活随笔為你收集整理的欧拉项目第五题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。