Divisibility: Not Just Modulus

Prime Hunting

I’m working on a Java program related to a Project Euler problem which asks you to find the largest prime factor of a very large composite, odd number.
I’ve already solved the problem in terms of the specific number that Euler gives; but now I am beginning to play around with some different ways of programming checks for divisibility by certain numbers.
In the process of determining whether or not a number is prime, we can expedite the process and rule out some composite numbers quickly by checking for divisibility by 2, 3, 5, and 7. I have omitted checks on divisibility by 4 because 4 is simply 22 or 2 x 2. Furthermore, 8 can be expressed as 23, or 2 x 2 x 2. So it is clear that if a number is divisible by 4 or 8, it is also divisible by 2.

Six follows in the same vein. Any number divisible by 6 is also divisible by 2 and 3. Take the number 18, for example.  It can be expressed as both 9 x 2 and 6 x 3. And 9 is merely 32, or 3 x 3.

For divisors < 10, we need only look to 2, 3, 5, and 7.

Divisibility by two/EVENNESS

I stumbled on Peteris Krumins’ blog post outlining the use of some Bitwise Operators in Java, and it gives an interesting and elegant solution for checking divisibility by 2, or evenness. I was so tired of the modulus option and doing logic operators on the binary directly is much more satisfying.

by three

Take the sum of all of the number’s digits. If this resulting sum is divisible by 3, then the number is divisible by 3. Again, this is infinitely more exciting than telling Java to just perform a mod 3 at the outset (for me at least)!

This is a method that takes the given integer as a parameter. The result of the integer mod 10 is added to the running sum; the integer is then divided by 10 and is assigned the value of that division (effectively truncating a 10’s place). (Thanks to my husband and fellow programmer Justin Thomas for clarifying this point for me.) The loop runs as long as n is greater than zero. I have this all run while n > 10 as well; this ensures that we will get down into single digits so that divisibility by 3 could be determined at a glance.


public static int SumOfDigits(int n) {
int sumDigits = 0;
while ( n > 10){
while ( n != 0 ) {
sumDigits += n % 10;
n /= 10;
}
}
return sumDigits;
}

Now we have the sum of the digits of the integer n. We need to check if this sum is divisible by 3.
At this point, the integer would be small enough to evaluate visually or by hand. We can just set the condition that n must equal 3, 6, or 9 to denote divisibility by 3 (we know n is under 10).


int sumResult = SumOfDigits(n);
if ( sumResult == 3 || sumResult == 6 || sumResult == 9 ) {
System.out.printf(“The integer %d is not prime.”, n);
return isPrime;
}

 I’ll follow up with checking divisibility by 7 later.

*note: I’m working on getting the code to format properly in WordPress. I’ll try to find a solution.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s