Question

java 一道算法题

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
呵呵 找到一个 改了一下O(∩_∩)O~

public static int getA(int m,int n){ //求最大公约数
int up=m<=n?m:n;//取m,n的较小者
int a=1;
for(int i=1;i<=up;i++){
if(m%i==0&&n%i==0)
a=i;
}
return a;
}
public static int getB(int m,int n){ //求最小公倍数
int b=m*n/getA(m,n);
return b;
}
public static void main(String[] args) {
Ahelp test=new Ahelp();
int sum=2;
for (int i = 3; i < 30; i++) {
sum=test.getB(sum, i);
}
System.out.println(sum);
}

Answer 1

public class Tst {

public static void main(String[] args) {

int num = 2520;

for(int i = 11; i <= 20; i++){
if(!isDivByNumLessThanTen(i)){
num *= i;
}
}

System.out.println(num);

}

private static boolean isDivByNumLessThanTen(int num) {
int count = 0;
for(int i = 1; i <= 10; i++){
if(num % i == 0){
count++;
}
}

return count >= 2;
}

}

-------------结果
116396280

算法，检测11~20，如果能被1~10整除超过2个数字，那么就代表可能可以被2520整除，就不相乘，否则相乘。

恩。这个算法有问题，问题出在，譬如12 = 2*6符合条件，但是14=2*7, 2得约分已经用了一次了，不符合条件，所以得改进。

Answer 2

public static void main(String[] args){

boolean flag = true;
int i = 0;
int j = 1;
while(flag){
j = 1;
i++;
while(i%j==0){
j++;
if(j>20){
flag = false;
}
}
}
//验证结果
for(int w = 1;w<=20;w++){
System.out.println(i+"/"+w+"="+i/w+"余数为"+i%w);
}
}
===================打印结果
232792560/1=232792560余数为0
232792560/2=116396280余数为0
232792560/3=77597520余数为0
232792560/4=58198140余数为0
232792560/5=46558512余数为0
232792560/6=38798760余数为0
232792560/7=33256080余数为0
232792560/8=29099070余数为0
232792560/9=25865840余数为0
232792560/10=23279256余数为0
232792560/11=21162960余数为0
232792560/12=19399380余数为0
232792560/13=17907120余数为0
232792560/14=16628040余数为0
232792560/15=15519504余数为0
232792560/16=14549535余数为0
232792560/17=13693680余数为0
232792560/18=12932920余数为0
232792560/19=12252240余数为0
232792560/20=11639628余数为0
==================================
2楼 116396280%16 = 8
=====================额写简单的还不给分啊
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class M {
public static void main(String[] args){
M m = new M();
int i = 2520;
int t = 2520;
for(int j=11;j<=20;j++){
if(i%j!=0){
t*=(m.getMaxNum(j,i)==-1?j:j/m.getMaxNum(j,i));
}
}
System.out.println(t);
}
/**
* 求两个数的最大公约数
* @param a
* @param b
* @return
*/
public int getMaxNum(int a,int b){
Set<Integer> l1 = getMaxNums(a);//a的约数集合
Set<Integer> l2 = getMaxNums(b);//b的约数集合
int k = -1;
for(int i : l1){
for(int j : l2){
if(i == j){
if(k<i){
k=i;
}
}
}
}
return k;
}

/**
* 求一个数的所有约数
* @param a
* @return
*/
public Set<Integer> getMaxNums(int a){
Set<Integer> l = new HashSet<Integer>();
for(int i = 2;i<a;i++){
if(a%i==0&&i<=a/2){
l.add(i);
}
}
return l;
}
}
======
打印结果232792560

Answer 3

我只是举个例子
比如 2,3,4的最小公倍数是12
那么求2,3,4,9的最小公倍数
我想大家都知道是36吧
那么用楼上的算法 就会测试12是否能整除9 不能
就拿12*9=108 这对么？

下面是求最小公倍数的程序 不符合LZ的题意 但是可以验证下结果
int l=20;
int[] a=new int[l];
for(int i=0;i<l;i++){
a[i]=i+1;
}
int s=1;
boolean b;
for(int i=2;i<=l;){
b=false;
for(int j=0;j<l;j++){
if(a[j]%i==0){
a[j]=a[j]/i;
b=true;
}
}
if(b){
s*=i;
}else{
i++;
}
}
System.out.println(s);

还有其实2楼的程序挺好的
不能被2520整除的数有
11
13
16
17
19
此时只要再把他们与2520 的最大公约数除去 相当于
2520*11*13*2*17*19就是了

追问

但是这种算法，当数据大时，比如是求200以下的，这样是不是就很麻烦呢，要算多少数的最大公约数？？？

追答

我想没什么改进了 这算最小公倍数 最大公约数 和 算π e一样 没什么好的算法 不然怎么能累死那么多数学叫兽

Answer 4

internal class Program { private static void Main(string[] args) { /*
* *
* 2520
* is
* the
* smallest
* number
* that
* can
* be
* divided
* by
* each
* of
* the
* numbers
* from
* 1 to
* 10
* without
* any
* remainder. *
* What
* is
* the
* smallest
* number
* that
* is
* evenly
* divisible
* by
* all
* of
* the
* numbers
* from
* 1 to
* 20?
*/ int[] numbers = Enumerable.Range(1, 20).ToArray(); int prime = 2; int nextPrime = 2; int nextPrimePow2 = 2*2; for (int i = 1; nextPrimePow2 < 20; i++) { int n = numbers[i]; if (n == 0) continue; for (int j = i + 1; j < numbers.Length; j++) { int k = numbers[j]; if (k%prime == 0) { numbers[j] = 0; continue; } if (prime == nextPrime) nextPrime = k; } prime = nextPrime; nextPrimePow2 = nextPrime*nextPrime; } var primes = numbers.Where(p => p != 0 && p != 1).ToArray(); var primeNums = new int[primes.Length]; numbers = Enumerable.Range(1, 20).ToArray(); for (int i = 0; i < numbers.Length; i++) { int n = numbers[i]; for (int j = 0; j < primes.Length; j++) { int item = primes[j]; int k = 0; for (; ; k++, n /= item) { if (n % item != 0) break; } if (primeNums[j] < k) primeNums[j] = k; } } long result = 1; for (int i = 0; i < primes.Length; i++) { Console.WriteLine("{0}*{1}", primes[i], primeNums[i]); result *= (long)Math.Pow(primes[i],primeNums[i]); } Console.WriteLine(result); } }

Answer 5

楼主这是在考验大伙的英语能力= =!
顶二楼