I put together a simple program in C++ that checks out whether or not a number is prime, i.e., whether or not it has any factors besides itself and 1. It was eventually writing a separate thing for this that helped me out, as despite what I'd learned in the past I was trying to make one program to do everything that was needed for the actual problem. Bad idea. Things are so much simpler if you break things up into their component parts...
Problem 7
Find the 10001st prime number. Once I had the program for checking whether or not a number is prime this was quite straightforward. I started off with knowing that 2 is the 1st prime number, and then working through all of the odd numbers after that and adding one to the tally every time that I found one.
Problem 41
What is the largest n-digit pandigital prime that exists? This was a little trickier, but not much more. It just took a bit of thinking. Firstly, what is a pandigital number? Well, a 5-digit pandigital number is, for example, 34251, a number which contains the first five digits once and once only. A 4-digit pandigital would be 4123 or 1234 or 3142, and so on. After a little thought, it occured to me that there cannot be 8- or 9-digit pandigital primes (if you're reading this Matt, do you know how/why that occurred to me?) and that the largest possible would be a 7-digit pandigital number, i.e., one that contained all the digits from one to seven.
It was then straightforward to think that it was most sensible to start searching from the extreme end of the numbers, 7654321, and to put conditions on the numbers; one only wants to check without 8, 9 or 0 in, one doesn't want duplicates of digits... Once I'd written those conditions in to the program, it was fine.
This takes my total of problems solved to nine. Sixteen to go. Might get one more done this weekend. It's good to keep thinking, and it also gives me a chance to keep learning bits and pieces of C++.
Keep learning people, it's the thing to do!
Saturday 10 January 2009
Project Euler, Problems 7 and 41
Subscribe to:
Post Comments (Atom)
3 comments:
Given a 9-digit pandigital number, the digits add to 45, meaning the number is divisible by 9; thus, the number cannot be prime. That one's easy.
It's not immediately obvious to me why there are no 8-digit pandigital primes. Certainly, if the last digit is even, 3, or 5, the number won't be prime. But when the number's last digit is 1 or 7... those cases will require a little more thought (although, perhaps I'm making this harder than it needs to be...I feel like I'm missing something obvious)
Also, I forgot I now have an actual username I could use when I post.
Ah... For similar reasons to 9-digit pandigitals: digits will sum to 36, also divisible by 9!
In fact, I eliminated 5- and 6-digit pandigitals because they add to multiples of 3, and I believe (though not sure I have ever proved for myself or seen a proof) that if the digits sum to a multiple of 3 then the number is a multiple of 3... I don't think that I'm making it up, fairly certain it is a true result! :)
Hahahahaha
When I was considering the 8-digit pandigital number, I took 45 and accidentally subtracted 8 instead of 9...... oops!
Post a Comment