Project Euler: Harshad Numbers
Go to Problem
It’s easy since I spent only 30+ minutes. So try it before read my thought and you’ll have some fun.
- I ‘guess’ it would be very slow to check all primes one by one.
- [1..9] are all Harshad numbers (seeds).
- Take one seed, add one digit to it and check if it’s valid. For example, take 2, check [20..29]. All valid numbers are new seeds.
- Check if a new seed is also a strong Harshad number.
- If a seed is a strong Harshad number, append one digit to it and check if it’s a ‘strong, right truncatable Harshad primes’. For example, 201 is a strong Harshad number, check if [2010..2019] are primes.
- Sum all valid primes, done.
- This is actually a tree structure, solve it with BFS.