int main(void)
{
unsigned long long n = 600851475143ULL;
unsigned long long i;
for (i = 2ULL; i < n; i++) {
while (n % i == 0) {
n /= i;
}
}
printf("%llu\n", n);
return 0;
}
Scannerin=newScanner(System.in);System.out.printf("Enter i Value: ");longn=in.nextLong();longnumber=n;longlargestPrimeFactor=n;longi=2;while(i<=n&&n!=1){if(n%i==0){n=n/i;largestPrimeFactor=i;}else{i=i+1;}}System.out.println("The largest prime factor of the number "+number+" is = "+largestPrimeFactor);
structPrimesIterator{found_primes:Vec<u64>,next_to_check:u64,}implPrimesIterator{fnnew()->Self{PrimesIterator{found_primes:Vec::new(),next_to_check:2,}}}implIteratorforPrimesIterator{typeItem=u64;fnnext(&mutself)->Option<u64>{fornuminself.next_to_check..{ifself.found_primes.iter().all(|prime|num%prime!=0){self.found_primes.push(num);self.next_to_check=num+1;returnSome(num);}}unreachable!()}}fngreatest_prime_divisor(mutnumber:u64)->u64{forprimeinPrimesIterator::new(){whilenumber%prime==0{number/=prime;}ifnumber<=1{returnprime;}}unreachable!()}fnmain(){letnumber=std::env::args().nth(1).expect("Number must be first argument");letnumber:u64=number.parse().unwrap();println!("The greatest prime divisor of {} is {}",number,greatest_prime_divisor(number));}
Result:
The greatest prime divisor of 600851475143 is 6857
I’m Erhan Kılıç, a curious web developer from Turkey who loves to write software applications and websites.
I have been working as a web developer since 2013.
<?php/**
* @Author: Erhan Kılıç
* @Website: http://erhankilic.org
* @Problem: The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* https://projecteuler.net/problem=3
*/classProblemSolver{private$original_number;private$number;private$current_prime_number=2;private$prime_numbers=[];private$largest_prime_number;/**
* ProblemSolver constructor.
* @param int $number
*/publicfunction__construct(int$number){$this->number=$this->original_number=$number;}/**
* Finds the next prime number
*/privatefunctionfind_next_prime_number(){if($this->current_prime_number==2){$this->current_prime_number++;}else{$this->current_prime_number+=2;}$can_divide=false;$number=2;while($number<$this->current_prime_number){if($this->current_prime_number%$number==0){$can_divide=true;}$number++;}if($can_divide){$this->find_next_prime_number();}}/**
* Finds the prime factors and largest prime factor of given number
*/publicfunctionfind_prime_factors(){while($this->number>0){if($this->number==1){$this->largest_prime_number=$this->current_prime_number;break;}else{if($this->number%$this->current_prime_number==0){$this->prime_numbers[]=$this->current_prime_number;$this->number/=$this->current_prime_number;}else{$this->find_next_prime_number();}}}echo$this->largest_prime_number;}}$solver=newProblemSolver(600851475143);$solver->find_prime_factors();
Javascript;
'use strict';/**
* @Author: Erhan Kılıç
* @Website: http://erhankilic.org
* @Problem: The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* https://projecteuler.net/problem=3
*/varnumber=600851475143,prime_number=2;functionfind_next_prime_number(){varcan_divide=false;varn=2;if(prime_number===2){prime_number++;}else{prime_number+=2;}while(n<prime_number){if(prime_number%n===0){can_divide=true;}n++;}if(can_divide){find_next_prime_number();}}while(number>1){if(number%prime_number===0){number/=prime_number;}else{find_next_prime_number();}}console.log(prime_number);
const isPrime = ( value ) => {
for( let i = 2; i < value; i++ )
if( value % i === 0 )
return false;
return true;
};
const LargestPrimeFactor = ( value ) => {
let result = [];
for( let i = 2; i < value; i++ )
if( isPrime( i ) )
if( value % i === 0 )
result.push( i );
return result;
};
console.log( LargestPrimeFactor( 600851475143 ) );
def isPrime( value ):
for i in range( 2, value ):
if value % i == 0:
return False
return True
def LargestPrimeFactor ( value ):
result = []
for i in range( 2, value ):
if isPrime( i ):
if value % i == 0:
result.append( i )
return result
print( LargestPrimeFactor( 600851475143 ) )
Java
import java.util.Arrays;
class Main {
public static void main(String[] args) {
class LargestPrimeFactor {
public LargestPrimeFactor( int value ) {
System.out.println(Arrays.toString(this.LargestPrimeFactor(value)));
}
boolean isPrime(int value) {
for(int i = 2; i < value; i++) {
if(value % i == 0) {
return false;
}
}
return true;
}
int[] LargestPrimeFactor(int value) {
int result[] = new int[4];
int counter = 0;
for( int i = 2; i < value; i++ ) {
if( this.isPrime(i) ) {
if(value % i == 0){
result[counter] = i;
counter++;
}
}
}
return result;
}
}
LargestPrimeFactor myObject = new LargestPrimeFactor(600851475143);
// [ 5, 7, 13, 29 ]
}
}
deflist_of_primes(n):not_prime=set()# In is O(1) rather than O(N)
primes=set()foriinxrange(2,n+1):ifinotinnot_prime:primes.add(i)# Adds multiples of the number to the set of checked values
# i * (i-1) etc. are already updated so starts at i*i
not_prime.update(range(i*i,n+1,i))returnprimesdefget_factors(n):factors=set()foriinxrange(1,int(n**0.5)):ifn%i==0:factors.add(i)factors.add(n/i)returnlist(factors)defget_prime_factors(n):factors=sorted(get_factors(n),reverse=True)primes=list_of_primes(factors[0])forfactorinfactors:iffactorinprimes:returnfactorelse:returnNoneprint(get_prime_factors(13195))
function isprime(n)
a = ceil(Int,sqrt(n))+1
a=iseven(a) ? a+1 : a
for i = a:-2:3
if n % i == 0
return false
end
end
return true
end
function largest_prime(number)
sqrt_of_n = ceil(Int,sqrt(number)) # the answer must be less than square root of n
sqrt_of_n=iseven(sqrt_of_n) ? sqrt_of_n+1 : sqrt_of_n #a prime cannot be even, so only check odd numbers
for i = sqrt_of_n:-2:1
if number % i == 0 #if 600851475143 is divisible by i
if isprime(i) #then check if i is prime
return i
break
end
end
end
end
but 600851475143 is coming under the range of the "long" data type of java but still it works for any value below it .
THE APPROACH IS PRETTY SIMPLE :
I used the the "Fundamental Theorem of Arithmetic" which states That Any Integer greater than 1 is either a prime number or product of prime numbers.
For example:
12
we start with smallest prime number 2.
the 12/2 = 6 which means that 2 is the prime factor 12.
If we try again by dividing the result by 2
6/2 = 3 . 3 is also a prime number . So the complete factorization is 2,2,3.
I have implemented this logic in the above code This works really fast .I think this code can be improved
a little bit Please some one suggest me.
Ruby✨💎✨
Nice one. But, I think y << prime, to_a.last pose addition execution time. Michael Kohl's approach is more optimized.
C :))
C is a powerful language. The same algorithm in Ruby shows to have time complexity issue. Good code, bro!
Java
PHP, again.
Solution: 6857
Python 3 solution. Inefficient I know...
Rust:
Result:
Scala:
Simple Rust solution
PHP;
Javascript;
Author: Brewyn
Largest Prime Factor
Javascript
const isPrime = ( value ) => { for( let i = 2; i < value; i++ ) if( value % i === 0 ) return false; return true; }; const LargestPrimeFactor = ( value ) => { let result = []; for( let i = 2; i < value; i++ ) if( isPrime( i ) ) if( value % i === 0 ) result.push( i ); return result; }; console.log( LargestPrimeFactor( 600851475143 ) );PHP
function isPrime( $value ) { for( $i = 2; $i < $value; $i++ ) if( $value % $i == 0 ) return false; return true; }; function LargestPrimeFactor ( $value ) { $result = []; for( $i = 2; $i < $value; $i++ ) if( isPrime( $i ) ) if( $value % $i == 0 ) array_push( $result, $i ); return $result; }; print_r( LargestPrimeFactor( 13195 ) ); //Array( // [0] => 5 // [1] => 7 // [2] => 13 // [3] => 29 //)Python
def isPrime( value ): for i in range( 2, value ): if value % i == 0: return False return True def LargestPrimeFactor ( value ): result = [] for i in range( 2, value ): if isPrime( i ): if value % i == 0: result.append( i ) return result print( LargestPrimeFactor( 600851475143 ) )Java
import java.util.Arrays; class Main { public static void main(String[] args) { class LargestPrimeFactor { public LargestPrimeFactor( int value ) { System.out.println(Arrays.toString(this.LargestPrimeFactor(value))); } boolean isPrime(int value) { for(int i = 2; i < value; i++) { if(value % i == 0) { return false; } } return true; } int[] LargestPrimeFactor(int value) { int result[] = new int[4]; int counter = 0; for( int i = 2; i < value; i++ ) { if( this.isPrime(i) ) { if(value % i == 0){ result[counter] = i; counter++; } } } return result; } } LargestPrimeFactor myObject = new LargestPrimeFactor(600851475143); // [ 5, 7, 13, 29 ] } }Python!
/*Largest prime factor
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?*/
include
using namespace std;
int main()
{
long long num=600851475143 ,largest=1 ;
for(int i=2;i<=num;i++)
{
if(num%i==0)
{
num=num/i;
cout< if(i>largest)
largest=i;
}
}
cout<<"\n\n"<<"the largest prime factor of the number 600851475143 is "<<largest<<"\n";
return 0;
}
My code in C++ >>Output>>6857
Julia
function isprime(n)
a = ceil(Int,sqrt(n))+1
a=iseven(a) ? a+1 : a
for i = a:-2:3
if n % i == 0
return false
end
end
return true
end
function largest_prime(number)
sqrt_of_n = ceil(Int,sqrt(number)) # the answer must be less than square root of n
sqrt_of_n=iseven(sqrt_of_n) ? sqrt_of_n+1 : sqrt_of_n #a prime cannot be even, so only check odd numbers
for i = sqrt_of_n:-2:1
if number % i == 0 #if 600851475143 is divisible by i
if isprime(i) #then check if i is prime
return i
break
end
end
end
end
println(largest_prime(600851475143))
How do I enter formatted code on this site?
Python:
C#
Result
It returns
2whenn = 1, my code returnsnil.java is cool
static long IsPrime(long n){
int counter = 2;
long newval = n;
long larfact = 0;
while(counter*counter <= n){
if(newval % counter == 0){
newval = newval/counter;
larfact = counter;
}
else{
counter++;
}
}
if(newval > larfact){
larfact = newval;
}
return larfact;
but 600851475143 is coming under the range of the "long" data type of java but still it works for any value below it .
THE APPROACH IS PRETTY SIMPLE :
I used the the "Fundamental Theorem of Arithmetic" which states That Any Integer greater than 1 is either a prime number or product of prime numbers.
For example:
12
we start with smallest prime number 2.
the 12/2 = 6 which means that 2 is the prime factor 12.
If we try again by dividing the result by 2
6/2 = 3 . 3 is also a prime number . So the complete factorization is 2,2,3.
I have implemented this logic in the above code This works really fast .I think this code can be improved
a little bit Please some one suggest me.
Hope You like The implementation ;)
python
Well optimized code. You had to think a lot. Good one, bro!