Problem 204

Comments

This problem seemed really simple. But because of the large range of numbers, it was actually very tough. I had to try several different ways of going about it before I could find one that didn’t require way too much memory.

What I ended up doing was going through all 10^9 numbers and seeing which were divisible by only the primes less than 100. I made a list of these primes, then divided them out of each number. When done going through all these primes, and dividing them all out, if the remaining number is 1, then I knew if fit the criteria. However, it took over 2 hours for this to run.

Code

def isprime(n):
	if n == 2:
		return True
	elif n < 2 or n%2 == 0:
		return False
	else:
		for i in range(3, int(n**0.5 + 1), 2):
			if n%i == 0: return False
		return True

def prime_list(low, high):
	primes = []
	for n in xrange(low, high):
		if isprime(n) == True:
			primes.append(n)
	return primes

primes = prime_list(2, 100)

count = 0
for n in xrange(1, 10**9+1):
	if n%10**5 == 0: print n, count
	for p in primes:
		while n%p == 0:
			n /= p
	if n == 1:
		count += 1

print count