CHALLENGE - Multiple of 1..n challenge

Question

Make a program that finds the smallest number that can be divided by each number in [1..n]

Brute force will be limited so you'll need to think a little bit about this.

Test 2520 for n=10
Test 232792560 for n=20

Answer 1

https://code.sololearn.com/cx0toQLjp6go/#java

Answer 2

gcd calculation speed depends of algorithm used to perform it ;P
... but I'm agree that gcd could be ALSO computed using euclidian algorithm and would be probably faster, but as I said, brute speed was not my main purpose (if this is a speed challenge, you should specify that: I solved the problem as it was first described), and gcd was not the most obvious way to implement my algorithm ^^

By the way, you finally let me find a way to get fun with your challenge, as I'm happy to have challenged myself by implementing a primes generator function using JS generator functions... rest was just accessory ;)

Answer 3

@VcC wrote: << So far i see neither ;-). >>

You're not honest: my second post describe an algorithm to be used... So, as you need prove, I have implemented it: not oneliner (there isn't real interest to do that, better to code clever primes code using generator function -- to help me find some fun ;P -- one prime factor utility function and one main function):

https://code.sololearn.com/WzNaddD278Y6/?ref=app

Answer 4

ah, that is about https://www.sololearn.com/Discuss/719426/?ref=app

Answer 5

@VcC: algorithm of @ysraelcon? He just suggested to look at its similar challenge (same but not necessarly with continuous range) thread for solutions provided there... he doesn't give a specific algorithm ^^

Anyway, speed can only be compared between same language and same device (and same compiler/interpreter context in any cases, same browser in case of web language, as each JS engine is differently implemented...), and brute speed was not my main purpose, just minimal efficiency (prime generator is particularly optimized, even if maybe not absolute quickest, as it's intensively used by my algorithm)

Answer 6

import java.util.*;
public class small
{
public static void main(String[]args)
{int i=0;
for( i=1;;i++)
{
if((i%1==0)&&(i%2==0)&&(i%3==0)&&(i%4==0)&&(i%5==0)&&(i%6==0)&&(""i%7==0)&&(i%8==0)&&(i%10==0)&&(i%9==0))
break;
}
System.out.println(i);
}
}

Answer 7

@VcC: There's no good code without proper algorithm... implementing one is not necessarly the easiest part, but that's not the main: given my explanation, the code is quite easy to done... well so, too much easy to make me fun to do it: just fun enough to think about the how-to way ;P

Answer 8

Here it is!

https://code.sololearn.com/c3M6WqOVMjtV/#cpp

Slow like a turtle but working.
From 19 onwards you need a pc.

Answer 9

@VcC: you're right... I was wrong (too quick and not completly awake ;P): it needs to remove numbers wich are divisor of others in the set (as 4 is already divisible by 2, if N is divisible by 4 it's also necessarly diviible by 2, and so on: so smallest number to be divisible by [1..10] is product of unique set of primary factors max use of each: [2,3,2×2,5,3×2,7,2×2×2,3×3,2×5] reduced to [2x2x2,3×3,5,7]... similar for [1..20] or whatever else ^^)

Answer 10

@VcC
my code works for every number, but you have to use a pc because SoloLearn server stop connections after a little amount of time.
"Time limit excedeed"

Answer 11

here some more solutions https://forum.freecodecamp.org/t/freecodecamp-algorithm-challenge-guide-smallest-common-multiple/16075

and key note: el algoritmo de Euclides

and here one algorithm of my friend @sayan https://code.sololearn.com/cY7MZPEKD4xD/?ref=app one liner :)

Answer 12

Looks like some one helped me posting my code...
thanks #@# Ysraelcon
i changed it a bit..
MERELY A 2 LINE CODE (one semicolon)

and 2nd code is EQUALLY EFFICIENT
##BUT NO MODULE USED##

https://code.sololearn.com/cY7MZPEKD4xD/?ref=app
https://code.sololearn.com/crQsMsgIuIEb/?ref=app

Answer 13

Answer to your "challenge" is mathematically answered by computation of factorials: 10! and 20!
https://en.m.wikipedia.org/wiki/Factorial
... because smallest number to be divisible by any factors is product of them, and factorial is definition of self product of continuous integers starting at one ^^

So this challenge is not << multiple >>... you can call it "multiply" challenge, or rather name it explicitly "factorial wap request" ;P

Answer 14

@VcC Yeah...Need to think about that.Will post it as soon as possible.

Answer 15

sure

Answer 16

Ruby code
https://code.sololearn.com/cJSclertXUu6/?ref=app

Answer 17

1) 2520
2) 232792560

Answer 18

I know ahahah I used an online tool XD

***laziness***

Answer 19

@napster Brute force attack!

Answer 20

Yes, @napster gave me a good idea.