Sololearn is struggling to run my code

Question

Hi guys 👋.
I made a code to calculate the largest prime factor of a number and it works fine for small numbers like 13195 but i wanna know the largest prime factor of 600851475143 but when i run it shows no output.
I get that sololearn is struggling to run my code.
But i really need to know the ans.
The code:
https://code.sololearn.com/ctAVPBDEwPUB/?ref=app
I think if the code is run in a powerful computer then I'll get the output. But I don't have one.

Answer 1

For a free cpu/gpu resource, you can try google colab, which is a jupyter notebook environment which can run your Python code in cloud.

https://colab.research.google.com

Answer 2

The prime factors of 600851475143 are [839, 71, 6857, 1471], so the largest prime factor is 6857. If you multiply all factors, you will get the input value: 839 * 71 * 6857 * 1471 == 600851475143

[edited]:
𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 ,To get prime factors of a value, you can use the sympy function primefactors() as demonstrated here:

from sympy import primefactors

n = 600851475143
pr_facts = primefactors(n)
print(f'prime factors of {n} are {pr_facts}') # result is [71, 839, 1471, 6857]

if you are forced to do it without module, the algorithm has to be adapted for max performance as already mentioned.

Answer 3

Namit Jain , you are absolutely right when you talk about learning and enhancing problem solving ability. This a must for all coders. But doing profession coding is something different. I always would rely on well-known and long-term supported modules.
Modules like sympy, numpy and so on, has highly optimized code. So why should i bark myself, when i have a dog who can do this better? 🙂

Answer 4

Yaah!! This happens many times even with recursions!

Answer 5

Namit Jain , yes - this was a typo and i have corrected it. Shame on me! 😁

Answer 6

Lothar suppose a person doesn't know about sympy then?
There should be an algorithm that can do this for you! Using py libraries don't enhance your problem solving ability 🤔

Making simplest and fastest ways to find answer:
https://code.sololearn.com/cH6Q6abXF9yC/?ref=app

Answer 7

If you want to further accelerate the calculation, you may want to change your algorithm. There are many ways to find prime numbers (not all of them are straightforward). Take a look at some related articles:

e.g.
https://stackoverflow.com/q/453793

Answer 8

𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 can help you

Answer 9

Thanks 𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 sir!
😊😊😊
can u explain your code pls

Answer 10

Nice explanation 👌👌👌
Thanks 𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥

Answer 11

NUHEEN ohh sorry!! It should be a prime factor! I forgot

Answer 12

NUHEEN now check it!
Can be said as one of the easiest way to do this problem!
Still some problem?

Answer 13

Nicely done Namit Jain

Answer 14

Checking if a number is prime by dividing by all numbers from 2 to n - 1 takes O(n) time. You can iterate up to math.sqrt(n) and reduce your time to O(sqrt(n)) which is far faster.

There are lots of optimizations possible with checking for primes but just that O(sqrt(n)) optimation is enough to calculate the result for this in a fraction of a second.

Here is an optimized version that runs in a fraction of a second:
import math

def is_prime(n):
max_i = int(math.sqrt(n))
if max_i * max_i == n:
return False # perfect squares are not prime.
else:
for i in range(2, max_i):
if n%i==0:
return False

return True

def largest_prime_factor(n):
factors = []
max_i = int(math.sqrt(n))
if is_prime(max_i) and max_i * max_i == n:
return max_i

for i in range(1,max_i):
if n%i==0:
if is_prime(i):
factors.append(i)
return max(factors)

print(largest_prime_factor(600851475143))

Answer 15

李立威 i tried colabatory according to u but it's taking forever to show the output!
Any other way?

Answer 16

𝐊𝐢𝐢𝐛𝐨 𝐆𝐡𝐚𝐲𝐚𝐥 sir can u help me solve this problem?

Answer 17

NUHEEN
Easy algorithm! Anyone can make it in just 2 minutes!
No modules imported

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

Answer 18

But Namit Jain your code doesn't give the correct output...
13195 should output 29

Answer 19

NUHEEN Sorry for the wrong code at the beginning! 'PRIME' just slipped off my mind!

Answer 20

Lothar shouldn't it be 6857