Posts Tagged with "Prime Generation"

10digitprimes

Project Euler 111: Search for 10-digit primes containing the maximum number of repeated digits.

Saturday, August 25, 2012

6 Comments

So in Problem 111 of Project Euler we are back at dealing with prime numbers. And rather large ones of them. But before going into details, here is the problem descriptionWe shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.Find the sum of all S(10, d).I rather quickly realized that there must be two solution approaches to this problem. Either we generate all the primes in the range and start finding the right ones. Or we can generate numbers with repeated digits and check if they are primes.I started out with the first approach, by trying to generate primes up to 10.000.000.000, but I ran into problems with my sieve as we have to index more than can be stored in an integer. So either I could rewrite the sieve or I could look into the other approach.

Continue reading...
Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

Project Euler 58: Investigate the number of primes that lie on the diagonals of the spiral grid

Saturday, August 27, 2011

9 Comments

In Problem 58 of Project Euler we are revisiting the spiral we worked on in Problem 28. I have since then learned that it is called an Ulam spiral after the Polish born American mathematician Stanislaw Ulam. The problem reads:What is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?In problem 28 we sought and found a closed form solution to finding the sum of the diagonals. In this problem we need to investigate each corner of the spiral. So we need to generate each corner an check it. I have found no other way than brute force to create the corners and check them. I found no pattern in the primes except that they never occurs in the lower right diagonal. The numbers there are always perfect squares due to the nature of the spiral.

Continue reading...

Project Euler 46: What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Saturday, June 4, 2011

10 Comments

Problem 46 of Project Euler readsWhat is the smallest odd composite that cannot be written as the sum of a prime and twice a square? I haven't found ways to solve this except for brute force, but I have found three slightly different approaches brute forcing the problem.

Continue reading...

Project Euler 35: How many circular primes are there below one million?

Saturday, April 9, 2011

7 Comments

In problem 35 of Project Euler we are back to primes., this time it is circular primes that we are focusing on. Before looking more at circular primes lets look at the problem description which reads How many circular primes are there below one million? At first I thought circular primes were any permutation of the prime, but then 791 would be in the example as well, so I realised that it is primes that you can rotate such that any rotation is also a prime. I must admit that I don't think I have found a very nice solution, but it runs fast enough to satisfy me. It is a brute force algorithm where we search every prime below 1.000.000 to see if it can be rotated.

Continue reading...

Sum of all Primes below 2000000 – Problem 10

Sunday, November 21, 2010

28 Comments

Problem 10 is all about primes, just like probem 7. The problem is Find the sum of all the primes below two million.I take three different approaches to the solution, and focus on Sieve of Eratosthenes, which I will present the source code for an optimized version of.

Continue reading...

Project Euler – Problem 7

Wednesday, November 3, 2010

3 Comments

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.What is the 10001st prime number?We could solve this by brute force checking all the numbers, or we could reuse part of the solution to problem 5, where we generated a list of primes using trial division with already found prime numbers.

Continue reading...