Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged

-3

n=10001 c=4 for i in range(11,1000000,2): d=0 for x in range(3,int(i**0.5)+1,2): if i%x==0: d=1 break if d==1: continue else: c+=1 if c==n: break print(i) ## Here is a simple approach to the question using python In my code i have taken c=4 which contains elements (2,...


1

def divisor_generator(n): '''Generates the divisiors of input num''' large_divisors = [] for i in range(1, int(math.sqrt(n) + 1)): if n % i == 0: yield i if i*i != n: large_divisors.append(n / i) for divisor in reversed(large_divisors): yield divisor I would rename this just divisors, ...


2

Breaking up comps results in simpler, more efficient, easier to control functions. Two lists (x,y) for a Cartesian product are usual. The products are half duplicates. If each column starts with a perfect square, the duplicates are eliminated. Then each column is generated. Each column starts with a perfect square but then must also be specifically trimmed ...


3

It's not clear to me why gen_primes() is so complicated. The C++ version, which is a straight sieve, is much clearer. There's one red flag in trial_division: /= is floating point division. Averaging timing runs would obviously be better, but even on a single timing run changing the two /= to //= drops the run time from 20.5 secs to 16.2 secs. The iteration ...


4

I think it looks pretty good. One possible way to make it faster is in this part: for ( int i = 0; i< k ; i++ ) { for ( int j = i; j< k ; j++ ) { int w = just_primes[i]+just_primes[j]; if ( w >= 1000000 && w <= 2000000 ) { p = w - 1000000; conjunct[p]++; } } } Notice that for each ...


3

For starters, you only need to check odd numbers (potential primes) below sqrt(X). If A*B=X, then either A=B and X is a perfect square, so the largest prime dividing A is the largest prime factor. OR, one of A and B is less than the other, and thus less than the sqrt(X). Without loss of generality, say A is less than B. Then B would be greater than the ...


1

You already skip all even numbers. For the same reason, create code that skips: every 3rd # every 5th # every 7th ... 11th ... 13th, maybe ...


3

It's buggy. Consider input 8. Also, consider an input which is a very large prime. E.g. 2147483647. Your current code would take about 2147483645 trial divisions. It's possible to do it with only 46340 trial divisions while keeping the code very simple. Can you see how? And that's easily optimised to 23171. Can you see how?


1

The first problem is that you are trying to find all prime numbers under number. The number of prime numbers under x is approximately x/ln(x) which is around 22153972243.4 for our specific value of x This is way too big ! So even if you where capable of obtaining each of these prime numbers in constant time it would take too much time. This tells us this ...


17

There are many questions about Project Euler 3 on this site already. The trick is to pick an algorithm that… Reduces n whenever you find a factor, so that you don't need to consider factors anywhere near as large as 600851475143 Only finds prime factors, and never composite factors, so that you never need to explicitly test for primality. Your algorithm ...


-2

You could calculate the upper bound based on Prime Number Theory. Once you have this number you can implement the Sieve of Eratosthenes. One possible implementation is using a HashTable with every number from 2 to your upperbound as the key and a bool indicating prime status for the value. Iterate through the sieve marking each number. As you find a new ...


Top 50 recent answers are included