We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #5: Smallest multiple
Project Euler #5: Smallest multiple
+ 0 comments import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int i = 0; i < t; i++){ int n = in.nextInt(); int ans = smallestDivisibleNumber(n); System.out.println(ans); } } private static int smallestDivisibleNumber(int n) { int ans = 1; for (int i = 2; i <= n; i++) { ans = lcm(ans, i); } return ans; } private static int lcm(int a, int b) { return (a * b) / gcd(a, b); } private static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); }
}
+ 0 comments Python Solution, I cut some factor processing through prime checking
import math def isPrime(n): if n == 1: return False if n % 2 == 0: return False for i in range(3, int(math.sqrt(n))+1, 2): if n % i == 0: return False return True for t in range(int(input())): n = int(input()) s = n while True: if not isPrime(s): for i in range(2, n + 1): if s % i != 0: break else: print(s) break if s % 2 == 1: s += 1 else: s += 2
+ 0 comments python 3
t = int(input().strip()) for a0 in range(t): n = int(input().strip()) num = 0 while True: num += 1 isOutput = True for i in range(1, n + 1): if num % i != 0: isOutput = False break if isOutput: break print(num)
+ 0 comments 100 points in just a millisecond:
1) find prime numbers from 1 to N. 2) find maximum power of prime number. 3) multiply each prime powers.
Hint: You dont need to calculate nonprime numbers because you always have enough primes to make them up
int result = 1; for (int i = 1; i <= n; i++) { if (isPrime(i)) { int r1 = 1; while (r1 * i <= n) r1 *= i; result *= r1; } } return result;
+ 0 comments import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { int n = sc.nextInt(); System.out.println(lcm(n)); } sc.close(); } private static BigInteger lcm(int n) { BigInteger lcm = BigInteger.valueOf(1); for (int i = 2; i <= n; i++) { lcm = lcm(lcm, i); } return lcm; } private static BigInteger lcm(BigInteger a, int b) { return a.multiply(BigInteger.valueOf(b)) .divide(a.gcd(BigInteger.valueOf(b))); } }
Load more conversations
Sort 224 Discussions, By:
Please Login in order to post a comment