C++

Forum

 
Does this work?

closed account (ETAkoG1T)
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!
Volatile Pulse (1543)
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.
closed account (ETAkoG1T)
Stupid me I forgot the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
inline int number_of_factors(long long count);
long long generate(long long count);
int main()
{
	using namespace std;
	long long i = 1;
	long long counter = 1;
	for(;number_of_factors(i) < 500;counter++)
	{
		i = i + counter + 1;
		cout << i << " : " << number_of_factors(i) << endl;
	}
	cout << "First number with 500 factors is " << i;
	cin.get();
	cin.get();
	return 0;
}
long long generate(long long count)
{
	long long total = 0;
	for(long long add = 0;add <= count;add++)
	{
		total += add;
	}
	return total;
}


int number_of_factors(long long count)
{
	int factors = 0;
	for(long long i = 1;i <= count;i++)
	{
		if(count % i == 0)
			factors++;
	}
	return factors;
}


What makes this work so slow! and does it work at all?
Volatile Pulse (1543)
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.
Last edited on
closed account (ETAkoG1T)
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.
Last edited on
cire (8284)
I implemented a sieve to solve that one.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Sloppy code for my solution, in case you get stumped and want to cheat: https://gist.github.com/4223571

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.
closed account (ETAkoG1T)
Isn't that formula to find prime numbers not triangle numbers...
cire (8284)
Yes, it is.

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.
closed account (ETAkoG1T)
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!
Last edited on
closed account (ETAkoG1T)
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
Last edited on
cire (8284)
Its stupid that they didn't atleast ask for something that don't take ages to find out.


It doesn't take ages to calculate. In fact, using the sieve and a little knowledge, it takes under a second for my computer to calculate the answer.

http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer
closed account (ETAkoG1T)
Ok you are probably right but if we just focus on this part:
1
2
3
4
5
6
7
8
9
10
 
int number_of_factors(long long count)
{
	int factors = 0;
	for(long long i = 1;i <= count;i++)
	{
		if(count % i == 0)
			factors++;
	}
	return factors;
}

I don't see how you could use this: http://www.wikihow.com/Determine-the-Number-of-Divisors-of-an-Integer to make it any faster. Unless ofcourse finding out the prime factors are faster. I don't see how you could implement it though, please explain.
cire (8284)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#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" ;
        }
        else
            break ;
    }
}
 
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


cire (8284)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
#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" ;
        }
        else
            break ;
    }
}
 
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!]
Last edited on
closed account (ETAkoG1T)
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
#include "stdafx.h"
#include <iostream>

unsigned primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
unsigned nPrimes = sizeof(primes)/sizeof(primes[0]) ;

unsigned getNumberOfDivisors( long long value )
{
    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 ;

        ++index ;
    }

    return nDivisors ;
}

int main()
{
	long long x = 1;
	long long count = 0;
    for ( ;getNumberOfDivisors(x) < 500;++count)
    {
		std::cout << x << " : " <<getNumberOfDivisors(x) << std::endl;
		x = x + count + 1;
	}
	std::cout << "answer: " << std::fixed << x;
	std::cin.get();
	std::cin.get();
}
cire (8284)
You're going to need a lot more primes.
closed account (ETAkoG1T)
Is the primes used for prime factorisation? How can I find primes in a good way?
cire (8284)
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.
Last edited on
closed account (ETAkoG1T)
This is my code now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
unsigned primes[99998];
unsigned nPrimes = sizeof(primes)/sizeof(primes[0]) ;
unsigned getNumberOfDivisors( long long value )
{
    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 ;

        ++index ;
    }

    return nDivisors ;
}

int main()
{
	long a, b;
	a = 1000000;
	b = 2;
	for(int counter = -1;counter < a;)
	{
		bool c = false;
		for(int o = 2;o < b;++o)
		{
			if(b % o == 0)
			{
				
				c = true;
				break;
			}
		}

		if(c)
		{		
			++b;
			continue;
		}
		++counter;
		primes[counter] = b;
		b++;
	}

	long long x = 1;
	long long count = 0;
    for ( ;getNumberOfDivisors(x) < 500;++count)
    {
		std::cout << x << " : " <<getNumberOfDivisors(x) << std::endl;
		x = x + count + 1;
	}
	std::cout << "answer: " << std::fixed << x;
	std::cin.get();
	std::cin.get();
}

I am not sure if it works, and if this is enough primes.
Last edited on
Topic archived. No new replies allowed.