# Tag Info

-2

def prime(n): for i in range(2,(n//2)+1): if n%i==0: return False return True def factor_pair(n): arr=[] for i in range(2,int(math.sqrt(n))+1): if n%i==0: arr.append((i,n//i)) return arr[-1] def downToZero(n): count=2 while(n>2): if prime(n)==True: n=n-1 ...

4

Timing The timer thread is unnecessary and an inaccurate way to measure time. I do now know about this system_clock, system calls might slow down the process (maybe the context switch even more though) Querying the time costs a bit of time, even if it does not involve an actual system call - which it really may not, there are lots of clever tricks for ...

3

The code does just a tad more then a standard sieve. Of course the inner loop of the sieve starts with i*i whereas your code starts with i*2; still we can expect that it should scale nicely with $O(n \log \log n)$ time complexity. Considering that a sieve over 200000000 completes in a matter of seconds, the difference must come from the work the sieve does ...

0

Consider what you are doing here. You are generating a list of primes less than a number. You are generating this list in order of increasing size. One simple optimization is to seed the list with a few primes at the beginning. In particular, 2 and 3. Then you iterate to skip over all the even numbers. That cuts your checks in half. Now, a second point ...

1

You should measure the duration of each step in the algorithm to detect where the bottleneck(s) is/are. You can do that using console.time("id") paired with console.timeEnd("id"): function findPrimes(count) { console.time("prime generation"); storePrimes(count); console.timeEnd("prime generation") ...

1

Improvement in function isprime: for(let i = 2; i <= number / 2; i++) can be for(let i = 2; i <= Math.round(Math.sqrt(number)) + 1 ; i++) Otherwise, the best easy to understand approach(in accordance to my knowledge) is to use the Sieve of Eratosthenes. Your problem can be a subset of the following problem Sieve of Eratosthenes JavaScript ...

0

You ask for speed up, so let's get timing data for the version you posted. I've appended this to your code from timeit import default_timer as timer args = (2, 1234567, 2345678) print(args) foo = gap(*args) def timedGap(): start = timer() gap(*args) end = timer() return end-start (timedGap() for dummy in range(1, 3)) timings = tuple((...

3

Depending on how large your lower and upper limits are, it may be faster to just generate all primes using a Sieve of Eratosthenes implementation. If the limits are beyond what is reasonable to generate all primes for, then primality testing such as Miller-Rabin is significantly faster than trial division. For example, gmpy2.is_prime.

4

First thing first, get rid of these ugly a and c. They do not add any value, but only obfuscate the code. def gap(p, q, m): """To generate gap in between two prime numbers""" """p is the difference,q is the lower limit where the list of numbers in between which prime is filtered,m is the upper limit""...

3

The most basic method of checking the primality of a given integer n is called trial division. This method divides n by each integer from 2 up to the square root of n. Any such integer dividing n evenly establishes n as composite; otherwise it is prime. Integers larger than the square root do not need to be checked because, whenever n=a * b, one of the two ...

4

First, some comments on your code: return d.append(b) is not very nice. You would think this function actually returns something, but this just returns None. Instead you modify a list being passed in as a parameter. This is a very C thing to do. Instead, just return the boolean value and use it to build a list using a list comprehension: d = [x for x in b ...

6

To be cheeky, the ultimate optimization is "don't use Python for numerics", and the next-best optimization is "use a library rather than writing this yourself". It's worth having a read through https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python Also consider calling into https://docs.sympy.org/...

Top 50 recent answers are included