Jump to content

  •  
  • Start New Topic
  • Log in with Facebook Log in with Twitter Log In with Google Log In with Steam      Sign In   
  • Create Account

Photo

Finding Total Number of Divisors [Java]


  • This topic is locked This topic is locked
9 replies to this topic

#1 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 15 December 2014 - 02:49 PM

For those coders out there, I've been playing around with the process of finding the total number of divisors of a number. This probably isn't the most efficient solution, but I found it really entertaining to think about and try to understand:

	private static int divisorsofN(long n) {
		ArrayList<long[]> primeFactorization = new ArrayList<long[]>();
		int totalDivisors = 1;

		for (long l = 2l; l <= n; l++) {
			if (isPrime(l) && n % l == 0) {
				boolean hitLimit = false;
				long[] factorization = new long[2];
				factorization[0] = l;
				while (hitLimit == false) {
					if (n % l == 0) {
						factorization[1]++;
						n /= l;
					} else {
						hitLimit = true;
					}
				}
				primeFactorization.add(factorization);
			}
		}

		for (int i = primeFactorization.size() - 1; i >= 0; i--) {
			totalDivisors *= (primeFactorization.get(i)[1] + 1);
		}

		System.out.println(totalDivisors);
		return totalDivisors;
	}

	public static boolean isPrime(long num) {
		for (long r = 2l; r < num; r++) {
			if (num % r == 0 && num != 2) {
				return false;
			}
		}
		return true;
	}

To understand what's going on here, check out this post: http://mathforum.org...view/55843.html

 

This could be implemented when faced with a problem such as #12 on Project Euler: https://projecteuler.net/problem=12

 

I'd love it if anyone came up with more efficient solutions - how could this be improved?

 

 

Thanks,

-Yak

 





#2 NameNo1Chose

NameNo1Chose
  • DG| 1st Lieutenant |1LT
  • 1,153 posts
  • LocationDallas, Tx
  • Games:Battlefield 3, Black Ops 2, Call of Duty 4, L4D 2, League of Legends, Minecraft

Posted 15 December 2014 - 08:03 PM

Oh man the good old days of coding. I haven't done much coding in about a year or two. I remember doing little projects like this all the time. Though I am a little more use to the syntax of C++ this looks like pretty decent code. You make me want to pull up my old engine projects I did. That was a ton of work and a lot of fun. I was only a couple classes away from doing my junior project that required a few thousand lines of code. Good luck to you in your Comp Sci Yak. It is a tough degree but I know you can do it!


Posted Image



#3 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 15 December 2014 - 10:28 PM

Oh man the good old days of coding. I haven't done much coding in about a year or two. I remember doing little projects like this all the time. Though I am a little more use to the syntax of C++ this looks like pretty decent code. You make me want to pull up my old engine projects I did. That was a ton of work and a lot of fun. I was only a couple classes away from doing my junior project that required a few thousand lines of code. Good luck to you in your Comp Sci Yak. It is a tough degree but I know you can do it!

I'm actually headed off to college for a Mech Engineering degree. I've been taking minors in comp sci for a while, though - it's definitely a fun hobby!

 

Thanks,

-Yak





#4 PhantomDot1

PhantomDot1
  • DG| 2nd Lieutenant |2LT
  • 1,637 posts

Steam Profile


         

Posted 16 December 2014 - 06:46 AM

Why do the ints in the for-loops start at 21 ? Maybe by trying to make less use of array lists and instead use a string added to a return string to add which divisor, and maybe as start of the string add the amount of divisors. I think by looking into that you could probably find a more efficient way to archieve this.

e.g.:

private static int divisorsofN(long inputnr)
{
	string which, output;
	int divisors = 0;

	for (int i = 1; i <= inputnr; i++)
	{
		if(inputnr % i == 0)
		{
			if(output == null)
			{
				string add = "" + i;
				which += add;
				divisors ++;
			}
			else
			{
				string add = " + " + i;
				which += add;
				divisors ++;
			}
		}
	}

	output = "the number of divisors is " + divisors + ". The divisors are " + which;
	return output;
}

Hell, You could even start those strings outside of the method, and make properties to retrieve them. If you remove the spaces around the +, you could retrieve those strings and cut them up at the +, giving u perfectly fine ints which are divisors of the input long to work with.


Edited by PhantomDot1, 16 December 2014 - 07:03 AM.

Posted Image



#5 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 17 December 2014 - 08:23 AM

Why do the ints in the for-loops start at 21 ? Maybe by trying to make less use of array lists and instead use a string added to a return string to add which divisor, and maybe as start of the string add the amount of divisors. I think by looking into that you could probably find a more efficient way to archieve this.

e.g.:

private static int divisorsofN(long inputnr)
{
	string which, output;
	int divisors = 0;

	for (int i = 1; i <= inputnr; i++)
	{
		if(inputnr % i == 0)
		{
			if(output == null)
			{
				string add = "" + i;
				which += add;
				divisors ++;
			}
			else
			{
				string add = " + " + i;
				which += add;
				divisors ++;
			}
		}
	}

	output = "the number of divisors is " + divisors + ". The divisors are " + which;
	return output;
}

Hell, You could even start those strings outside of the method, and make properties to retrieve them. If you remove the spaces around the +, you could retrieve those strings and cut them up at the +, giving u perfectly fine ints which are divisors of the input long to work with.

They start at 2, the notation for longs is "num" + "lowercase L"

 

I've gotta run off to an exam, but I'll check out your code later!

 

Thanks,

-Yak





#6 NameNo1Chose

NameNo1Chose
  • DG| 1st Lieutenant |1LT
  • 1,153 posts
  • LocationDallas, Tx
  • Games:Battlefield 3, Black Ops 2, Call of Duty 4, L4D 2, League of Legends, Minecraft

Posted 17 December 2014 - 11:56 AM

Nicely done Phantom. The less lines of code the better.


Posted Image



#7 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 17 December 2014 - 02:34 PM

Why do the ints in the for-loops start at 21 ? Maybe by trying to make less use of array lists and instead use a string added to a return string to add which divisor, and maybe as start of the string add the amount of divisors. I think by looking into that you could probably find a more efficient way to archieve this.

e.g.:

private static int divisorsofN(long inputnr)
{
	string which, output;
	int divisors = 0;

	for (int i = 1; i <= inputnr; i++)
	{
		if(inputnr % i == 0)
		{
			if(output == null)
			{
				string add = "" + i;
				which += add;
				divisors ++;
			}
			else
			{
				string add = " + " + i;
				which += add;
				divisors ++;
			}
		}
	}

	output = "the number of divisors is " + divisors + ". The divisors are " + which;
	return output;
}

Hell, You could even start those strings outside of the method, and make properties to retrieve them. If you remove the spaces around the +, you could retrieve those strings and cut them up at the +, giving u perfectly fine ints which are divisors of the input long to work with.

Yeah, this is definitely an interesting idea. The idea behind mine was to not have to count each divisor individually, but this seems to count them each and do it efficiently as well!

 

Thanks,

-Yak





#8 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 17 December 2014 - 09:25 PM

Now this is interesting... Here's the full code I'm running:

import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {
		long count = 0l;
		long startTime = System.currentTimeMillis();

		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (divisorsofN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		count = 0l;
		System.out.println("Yak's Solution: " + (System.currentTimeMillis() - startTime));
		startTime = System.currentTimeMillis();
		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (phantomOfN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		System.out.println("Phantom Solution: " + (System.currentTimeMillis() - startTime));
	}

	private static int phantomOfN(long n) {
		String output = null;
		int divisors = 0;

		for (long l = 1l; l <= n; l++) {
			if (n % l == 0) {
					divisors++;
			}
		}
		return divisors;
	}

	private static int divisorsofN(long n) {
		ArrayList<long[]> primeFactorization = new ArrayList<long[]>();
		int totalDivisors = 1;

		for (long l = 2l; l <= n; l++) {
			if (isPrime(l) && n % l == 0) {
				boolean hitLimit = false;
				long[] factorization = new long[2];
				factorization[0] = l;
				while (hitLimit == false) {
					if (n % l == 0) {
						factorization[1]++;
						n /= l;
					} else {
						hitLimit = true;
					}
				}
				primeFactorization.add(factorization);
			}
		}

		for (int i = primeFactorization.size() - 1; i >= 0; i--) {
			totalDivisors *= (primeFactorization.get(i)[1] + 1);
		}
		return totalDivisors;
	}

	public static boolean isPrime(long num) {
		for (long r = 2l; r < num; r++) {
			if (num % r == 0 && num != 2) {
				return false;
			}
		}
		return true;
	}

	/*
	 * private static boolean hasTonsOfDivisors(long currentTriangle) { int
	 * numDivisors = 0; for (long i = 1l; i < currentTriangle / 2; i++) { if
	 * (currentTriangle % i == 0) { numDivisors++; } }
	 * System.out.println(currentTriangle + " :: " + numDivisors); if
	 * (numDivisors > 500) { return true; } return false;
	 * 
	 * }
	 */
}

The console reads this when the script is over:
 
76576500
Yak's Solution: 94439
76576500
Phantom Solution: 3760000
 
Naturally this is with a huge number (Looking for one with 500 divisors), but it seems to show that while Phantom's bit is shorter and less complex, it takes longer to run.
 
Thanks,
-Yak




#9 PhantomDot1

PhantomDot1
  • DG| 2nd Lieutenant |2LT
  • 1,637 posts

Steam Profile


         

Posted 18 December 2014 - 04:12 AM

 

Now this is interesting... Here's the full code I'm running:

import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {
		long count = 0l;
		long startTime = System.currentTimeMillis();

		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (divisorsofN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		count = 0l;
		System.out.println("Yak's Solution: " + (System.currentTimeMillis() - startTime));
		startTime = System.currentTimeMillis();
		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (phantomOfN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		System.out.println("Phantom Solution: " + (System.currentTimeMillis() - startTime));
	}

	private static int phantomOfN(long n) {
		String output = null;
		int divisors = 0;

		for (long l = 1l; l <= n; l++) {
			if (n % l == 0) {
					divisors++;
			}
		}
		return divisors;
	}

	private static int divisorsofN(long n) {
		ArrayList<long[]> primeFactorization = new ArrayList<long[]>();
		int totalDivisors = 1;

		for (long l = 2l; l <= n; l++) {
			if (isPrime(l) && n % l == 0) {
				boolean hitLimit = false;
				long[] factorization = new long[2];
				factorization[0] = l;
				while (hitLimit == false) {
					if (n % l == 0) {
						factorization[1]++;
						n /= l;
					} else {
						hitLimit = true;
					}
				}
				primeFactorization.add(factorization);
			}
		}

		for (int i = primeFactorization.size() - 1; i >= 0; i--) {
			totalDivisors *= (primeFactorization.get(i)[1] + 1);
		}
		return totalDivisors;
	}

	public static boolean isPrime(long num) {
		for (long r = 2l; r < num; r++) {
			if (num % r == 0 && num != 2) {
				return false;
			}
		}
		return true;
	}

	/*
	 * private static boolean hasTonsOfDivisors(long currentTriangle) { int
	 * numDivisors = 0; for (long i = 1l; i < currentTriangle / 2; i++) { if
	 * (currentTriangle % i == 0) { numDivisors++; } }
	 * System.out.println(currentTriangle + " :: " + numDivisors); if
	 * (numDivisors > 500) { return true; } return false;
	 * 
	 * }
	 */
}

The console reads this when the script is over:
 
76576500
Yak's Solution: 94439
76576500
Phantom Solution: 3760000
 
Naturally this is with a huge number (Looking for one with 500 divisors), but it seems to show that while Phantom's bit is shorter and less complex, it takes longer to run.
 
Thanks,
-Yak

 

Originally, I had to make a similiar script like I wrote for c#, not for java. Yet since they're so similiar, the code works in java too. Also note that I am a first year game tech student, calculations about which scripts run faster are further down the road :). Interesting bit of information though, that your code is more complex, yet runs faster.

 

Another thing I'd like to note is that in c#, my code would have less work for garbage collection than yours, yet I am not sure whether garbage collection works like that in java as well.


Edited by PhantomDot1, 18 December 2014 - 04:14 AM.

Posted Image



#10 agent yak

agent yak
  • DG| 1st Lieutenant |1LT
  • 1,228 posts
  • LocationMassachusetts, USA
  • Games:Arma 2, Arma 3, DayZ, Battlefield 3, Battlefield 4, Black Ops 2, Call of Duty 4, CS:GO, Diablo 3, L4D 2, Minecraft, Red Orchestra 2, Rust, Starcraft 2

Posted 18 December 2014 - 08:23 AM

 

 

Now this is interesting... Here's the full code I'm running:

import java.util.ArrayList;

public class Main {

	public static void main(String[] args) {
		long count = 0l;
		long startTime = System.currentTimeMillis();

		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (divisorsofN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		count = 0l;
		System.out.println("Yak's Solution: " + (System.currentTimeMillis() - startTime));
		startTime = System.currentTimeMillis();
		while (true) {
			long currentTriangle = 0;
			for (long i = 0l; i <= count; i++) {
				currentTriangle += i;
			}
			if (phantomOfN(currentTriangle) > 500) {
				System.out.println(currentTriangle);
				break;
			}
			count++;
		}
		System.out.println("Phantom Solution: " + (System.currentTimeMillis() - startTime));
	}

	private static int phantomOfN(long n) {
		String output = null;
		int divisors = 0;

		for (long l = 1l; l <= n; l++) {
			if (n % l == 0) {
					divisors++;
			}
		}
		return divisors;
	}

	private static int divisorsofN(long n) {
		ArrayList<long[]> primeFactorization = new ArrayList<long[]>();
		int totalDivisors = 1;

		for (long l = 2l; l <= n; l++) {
			if (isPrime(l) && n % l == 0) {
				boolean hitLimit = false;
				long[] factorization = new long[2];
				factorization[0] = l;
				while (hitLimit == false) {
					if (n % l == 0) {
						factorization[1]++;
						n /= l;
					} else {
						hitLimit = true;
					}
				}
				primeFactorization.add(factorization);
			}
		}

		for (int i = primeFactorization.size() - 1; i >= 0; i--) {
			totalDivisors *= (primeFactorization.get(i)[1] + 1);
		}
		return totalDivisors;
	}

	public static boolean isPrime(long num) {
		for (long r = 2l; r < num; r++) {
			if (num % r == 0 && num != 2) {
				return false;
			}
		}
		return true;
	}

	/*
	 * private static boolean hasTonsOfDivisors(long currentTriangle) { int
	 * numDivisors = 0; for (long i = 1l; i < currentTriangle / 2; i++) { if
	 * (currentTriangle % i == 0) { numDivisors++; } }
	 * System.out.println(currentTriangle + " :: " + numDivisors); if
	 * (numDivisors > 500) { return true; } return false;
	 * 
	 * }
	 */
}

The console reads this when the script is over:
 
76576500
Yak's Solution: 94439
76576500
Phantom Solution: 3760000
 
Naturally this is with a huge number (Looking for one with 500 divisors), but it seems to show that while Phantom's bit is shorter and less complex, it takes longer to run.
 
Thanks,
-Yak

 

Originally, I had to make a similiar script like I wrote for c#, not for java. Yet since they're so similiar, the code works in java too. Also note that I am a first year game tech student, calculations about which scripts run faster are further down the road :). Interesting bit of information though, that your code is more complex, yet runs faster.

 

Another thing I'd like to note is that in c#, my code would have less work for garbage collection than yours, yet I am not sure whether garbage collection works like that in java as well.

 

Java does have garbage collection, if that's what you're asking. I'm just saying it's interesting to see that what looks like a very simple solution might not always be the fastest.

 

I'm big on efficiency of code, so I'm always looking for ways to improve my programs!

 

 

Thanks,

-Yak








0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users

')
Change Theme!