This program has been running for quite some time now! I am looking for the first triangle number that has over 500 factors. I hope I haven't waited all this time for nothing!
I assume you're working on one of the Project Euler problems. I'd end the program if you waited for more than 15 minutes. I personally only wait 5, but to each their own.
You need to test it with small numbers first just to make sure you're not running an infinite loop/recursion. Another thing to check is to make sure you don't go out of bounds, but I don't believe there is an issue with that.
You're bruteforcing it. It's going to take a while to eventually get to the end, but you would. I wouldn't suggest waiting for it to find the right answer though. I'd reevaluate your algorithm.
Edit: On second thought, I don't know that it would eventually get you there. Let me find what I used...if I ever did that one -.-
Edit: I also used a brute force technique. I didn't write down the time, but mine is faster since it doesn't output every triangle and their factors. I'm still running your program after several minutes and still no answer. I believe I let mine run for about 30 mins on my computer when I finally got the answer.
What algorythm would you use? I have waited for 4 hours now but I just cancelled because I understood it wouldn't get high enough :/ I need some help with getting a more effective algorythm.
The sieve implementation isn't very clean. I'm pretty sure I had it in mind to make the sieve's progress saveable and resumable, which partially explains the crappy design, but it's sort of readable.
The problem is only tangentially about finding triangle numbers. Mostly it's about finding the number of divisors. To find the number of divisors, it helps to know which primes the number is evenly divisible by.
If you're going to brute force it, you should at least cache the primes as you calculate so you aren't calculating the same primes over and over and over again.
Does odd numbers in general have less factors? because then you could just not calculate any odd numbers... :/ Im not sure though, but even numbers can be divided by some odd numbers and some odd numbers, while odd numbers can never be divided by even numbers :)
(even with that prime thing you have I don't think it would speed it up enough to do it in under 10 min. Only a little partion of the numbers are primes. I think I would have to change the formula totally! Its stupid that they didn't atleast ask for something that don't take ages to find out. Example: first triangular number with 200 factors, my computer would be able to handle that!
Ok just give me a triangular number not too far below the answer to the problem(like 10 triangle numbers below, if you understand what I mean, without telling me the answer) so that I can check that the program works. Thank you so much, I hope you continue to help me with my project euler problems, I am only 14 years so every time I do a problem I get really happy:P
#include <iostream>
unsigned primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
unsigned nPrimes = sizeof(primes)/sizeof(primes[0]) ;
unsigned getNumberOfDivisors( unsigned value )
{
unsigned steps = 0 ;
unsigned index = 0 ;
unsigned nDivisors = 1 ;
while (index < nPrimes && value > 1 )
{
unsigned exponent = 0 ;
while ( value % primes[index] == 0 )
{
value /= primes[index] ;
++exponent ;
}
if ( exponent )
nDivisors *= exponent+1 ;
steps += exponent ;
++index ;
}
steps += index-1 ;
std::cout << "Took " << steps
<< " steps to find the number of divisors.\n" ;
return nDivisors ;
}
int main()
{
for ( ; ; )
{
int input ;
std::cout << "Enter a (reasonably small) number: " ;
std::cin >> input ;
if ( std::cin && input > 1 )
{
std::cout << input << " has "
<< getNumberOfDivisors(input) << " divisors\n" ;
}
elsebreak ;
}
}
Enter a (reasonably small) number: 60
Took 6 steps to find the number of divisors.
60 has 12 divisors
Enter a (reasonably small) number: 100
Took 6 steps to find the number of divisors.
100 has 9 divisors
Enter a (reasonably small) number: 45360
Took 13 steps to find the number of divisors.
45360 has 100 divisors
Contrast that with the brute force approach. Note that I made one small optimization from your implementation. I reduced the number of times the for loop in your number_of_factor function by about half, so consider how much larger the numbers might be:
#include <iostream>
unsigned getNumberOfDivisors( unsigned value )
{
unsigned nDivisors = 1 ;
unsigned i ;
for( i = 1; i <= value/2; ++i )
{
if ( value % i == 0 )
++nDivisors ;
}
std::cout << "Took " << i
<< " steps to find the number of divisors\n" ;
return nDivisors;
}
int main()
{
for ( ; ; )
{
int input ;
std::cout << "Enter a (reasonably small) number: " ;
std::cin >> input ;
if ( std::cin && input > 1 )
{
std::cout << input << " has "
<< getNumberOfDivisors(input) << " divisors\n" ;
}
elsebreak ;
}
}
Enter a (reasonably small) number: 60
Took 31 steps to find the number of divisors
60 has 12 divisors
Enter a (reasonably small) number: 100
Took 51 steps to find the number of divisors
100 has 9 divisors
Enter a (reasonably small) number: 45360
Took 22681 steps to find the number of divisors
45360 has 100 divisors
[Edit: Oops. Small mistake. That should've been division, not multiplication. Have it fixed in a sec. Fixed!]
I tested it but the number of divisors is really low, I think they are lower than they should be, know why? I tried your program it worked fine this is my code:
Is the primes used for prime factorisation? How can I find primes in a good way?
I gave you a link that explains how the primes are used. I gave you code that showed you how the primes are used. I gave you a link to code that shows you one way to find primes (and solve the problem in question,) although in this case a brute force approach is doable.
Maybe you should actually piece it all together and quit asking questions you already have answers to. Use google. Write code.