本帖最后由 B1tetheDust 于 2022-3-16 19:43 编辑
import time
import math
# Method 1-------------------------------------------------------------------------------------------------------------#
def func1(num_range):
divisors =
is_divisible = min_div_num = 0
while not is_divisible:
min_div_num += 30
is_divisible = min((min_div_num % num == 0) for num in divisors)
return min_div_num
# Method 2-------------------------------------------------------------------------------------------------------------#
def find_prime(a_num):
is_prime = 1
for i in range(2, int(math.sqrt(a_num) + 1)):
if a_num % i == 0:
is_prime = 0
return is_prime
def func2(num_range):
divisors =
primes =
mult = 1
for k in primes:
mult *= k
min_div_num = is_divisible = 0
while not is_divisible:
min_div_num += mult
is_divisible = min((min_div_num % num == 0) for num in divisors)
return min_div_num
# Method 3-------------------------------------------------------------------------------------------------------------#
def gcd(num_a, num_b):
if num_a == num_b:
return num_a
elif num_a < num_b:
num_a, num_b = num_b, num_a
return gcd(num_a, num_b)
else:
mod_a, mod_b = num_a & 1, num_b & 1
if mod_a and mod_b:
return gcd(num_b, num_a - num_b)
elif not mod_a and mod_b:
return gcd(num_a >> 1, num_b)
elif mod_a and not mod_b:
return gcd(num_a, num_b >> 1)
else:
return gcd(num_a >> 1, num_b >> 1) << 1
def lcm(num_a, num_b):
gcdivisor = gcd(num_a, num_b)
return (num_a * num_b) / gcdivisor
def func3(num_range):
lcmultiple = 1
for i in range(1, num_range + 1):
lcmultiple = lcm(int(lcmultiple), int(i))
return lcmultiple
# Method 4-------------------------------------------------------------------------------------------------------------#
def gcd1(num1, num2):
if num1 < num2:
num1, num2 = num2, num1
while num2 != 0:
num1, num2 = num2, num1 % num2
return num1
def lcm1(num1, num2):
gcdivisor = gcd1(num1, num2)
a = num1 * num2 / gcdivisor
return a
def func4(num_range):
lcmultiple = 1
for i in range(1, num_range + 1):
lcmultiple = lcm1(int(lcmultiple), int(i))
return lcmultiple
#----------------------------------------------------------------------------------------------------------------------#
test_num = 20
#----------------------------------------------------------------------------------------------------------------------#
start1 = time.perf_counter()
print('The smallest positive number is %d' % func1(test_num))
print('Method 1 takes %f s' % (time.perf_counter() - start1))
#----------------------------------------------------------------------------------------------------------------------#
start2 = time.perf_counter()
print('The smallest positive number is %d' % func2(test_num))
print('Method 2 takes %f s' % (time.perf_counter() - start2))
#----------------------------------------------------------------------------------------------------------------------#
start3 = time.perf_counter()
print('The smallest positive number is %d' % func3(test_num))
print('Method 3 takes %f s' % (time.perf_counter() - start3))
#----------------------------------------------------------------------------------------------------------------------#
start4 = time.perf_counter()
print('The smallest positive number is %d' % func4(test_num))
print('Method 4 takes %f s' % (time.perf_counter() - start4))
前两个是自己想的，后面两个都借鉴了别人的算法，最快的是Method 4，还是别人的方法快。Sigh.
Rust + Rayon并行无脑暴算：
use rayon::prelude::*;
use std::time::Instant;
fn main() {
let now = Instant::now();
let mut start = 1;
let mut i = None;
while i == None {
i = (start..start+1000)
.into_par_iter()
.filter(|x| check(*x))
.min();
start += 1000;
}
println!("最小数字是{:?}", i);
println!("耗时{}毫秒。", now.elapsed().as_millis())
}
fn check(num: i32) -> bool {
for i in 1..21 {
if num % i != 0 {
return false;
}
}
true
}
---
最小数字是Some(232792560)
耗时3147毫秒。
能把Rust写的这么慢的只有我了{:10_266:}
#include <stdio.h>
/*
2520 是最小的能被 1-10 中每个数字整除的正整数。
最小的能被 1-20 中每个数整除的正整数是多少？
*/
int divisor(int num, int d) {
return (num / d == (float)num / (float)d);
}
int count(int n, int x) {
for (int i = 1; i <= x; i++)
if (!divisor(n, i))
return 0;
return 1;
}
int main() {
int i = 1;
while (!count(i, 20))
i++;
printf("%d", i);
return 0;
}
希望大神指出优化方法
#include <stdio.h>
/*
2520 是最小的能被 1-10 中每个数字整除的正整数。
最小的能被 1-20 中每个数整除的正整数是多少？
*/
#define ll long long
int divisor(ll int num, ll int d) {
return (num / d == (double)num / (double)d);//float好像放不下一些大的值
}
int count(int n, int x) {
if (!n)
return 0;
for (int i = 1; i <= x; i++)
if (!divisor(n, i))
return 0;
return 1;
}
int main() {
ll int i = 6, max = 10;
ll int t = 0;
for (int j = 2; j <= max; j++)
if (j % 2 != 0)
if (j % 3 != 0)
i *= j;
while (!count(t, max))
t += i;
printf("%lld", t);
return 0;
}
1ms
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b)
{
return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b)
{
return a*b/gcd(a,b);
}
int main()
{
LL ans = 1;
for(int i=1;i<=20;i++) ans = lcm(ans,i);
cout<<ans<<endl;
return 0;
}
#include<stdio.h>
#include<math.h>
int Determine(int i);
int Determine(int i)
{
int n;
if(i==1)
{
return 0;
}
if(i==2)
{
return i;
}
else if(i%2==0)
{
return 0;
}
else
{
for(n=2;n<=pow(i,0.5);n++)
{
if(i%n==0)
{
return 0;
}
}
return i;
}
}
int main(void)
{
int i,k;
unsigned long long int sum=1;
for(i=1;i<=20;i++)
{
k=Determine(i);
if(k)
{
for(k;k*k<=20;k=k*k)
{
;
}
printf("%d\n",k);
sum=sum*k;
}
}
printf("最小的能被 1-20 中每个数整除的正整数是%lld\n",sum);
return 0;
}
//思路
/*
2->2
3->3
2->4
5->5
7->7
2->8
3->9
11->11
13->13
2->16
17->17
19->19
利用一个定理，任何一个合数都可以拆成 质数积 形式，用集合(且可以多同一元素)取并集
还可以质数的次方判断
但必须引入一个纯合数的概念，质数积 形式=全部为同一个质数。
在它的前面，不可能有比它还需要（在数量上）这同一个质数的数了
*/
for i in range(2520, 1000000000):
for j in range(10, 21):
if i % j == 0:
if j == 20:
print(i)
break
else:
break
答案是232792560，算法耗时比较长
c++ 练习
#include <iostream>
using namespace std;
int multiple(int a, int b);
int main() {
int a = 2;
for (int i = 3; i <= 20; i++) {
a = multiple(a, i);
}
cout << a << endl;
return a;
}
int multiple(int a, int b) {
if (a > b) {
return multiple(b, a);
}
int m = b;
while (m % a || m % b) {
m = m + b;
}
return m;
}