8
donuts
7y

I spend all morning on trying to solve an Algo problem for upcoming interview practice (Euler #3) that comes down to implementing IsPrime.

I remember reading once how Sieve of Eratosthenes

Isa the right way to go do when I first started I wanted to use that.

Then I couldn't think of the right code though so I went with Brute Force (for all numbers upto X see X is divisible by it)

It actually worked but I wanted to just try the "right way".

It's way slower and actually ended up with the wrong answer...

But at this point I don't give a **** anymore.

I guess lesson learned... Use Brute Force first... Then optimise for a problem more elegant solution.

Comments
  • 2
    You could have just checked till sqrt(x)
  • 0
    @damsehgal that I did, still slow...

    The sqrt was like 7 million
  • 0
    You don't try all numbers up to 7 millions.

    You try all primes up to 7 millions.
    To get those you recursively follow same procedure
  • 0
    @repstosd great, how do you know a number is prime?
  • 0
    Primality test would be a good place to start
  • 0
    @noctemx yes and the implementation would be... Point was in order to find prime have to try all numbers... Not just the primes
  • 0
    @billgates just trying to help in the "how to know if a number is prime" question
  • 1
    You start with 2 and 3 in a list
    Count upward
    Every time check divisibility against the items in list
    If all fail, add this to the list
    Repeat
  • 1
    @billgates
    You can just save a seive of all primes till 7million. Can be done in less than 1 sec. For even better results, there exist optimized seive of Eratosthenes which uses bitwise operators. Just check your number is not divisible by all primes(approx 7million/ln(7million)).
  • 0
    @damsehgal hm... Maybe I implemented it wrong then....
Add Comment