Divisibility: Not Just Modulus (2)

As promised in my last post, here I will explore divisibility by 7 (and 5) without relying exclusively on the modulus operator.

Divisibility by 5

Divisibility by 5 can be determined by examining the last digit of an integer. If it is a 5 or a 0, then the integer is divisible by 5.
This seems simple enough, but if we are evaluating the divisibility by 5 of a previously unknown integer, then we must tell Java how to determine the length of this incoming integer. If the length is known, then we can instruct Java to look at the last character in the string and see if it is a 0 or 5.

I wrote this snippet to solve the problem. This code assumes a Scanner object that reads int n, inputted by the user, and also a running status String, aptly named….status.

blog_1_12It also returns the quotient of integer n divided by 5.

Divisibility by 7

This one is fun. One known algorithm to determine divisibility by 7 is to take the last digit of an integer, double it, subtract it from the truncated original integer, and repeat until a single digit remains. If that digit is 0 or 7, then the original integer is divisible by 7.

Example: 693

3 x 2 = 6

69 – 6 = 63

3 x 2 = 6

6 – 6 = 0

The integer 693 is divisible by 7.

What follows is a rather massive chunk of code. I believe it can be streamlined, perhaps even into a nice and tidy recursive solution, but I just got it working and am pretty excited about it.

The first part:

blog_1_12_2At this point, we have grabbed the last digit, doubled it, and rebuilt the source number minus that final digit. We’re ready to subtract the doubled final digit from the source number.

blog_1_12_3Notice that at the end of the loop, we increment the counter. The while loop hinges on there still remaining at least one place.

Also, at the end, I just took the absolute value of the result mod 7 to determine divisibility. Think of the number 14. Doubling 4 yields 8; 1 – 8 = -7. This also indicates a multiple of 7. Or how about 28? 2 -16 = -14. Again, we have a multiple of 7. The absolute value becomes important here.

Combined, I have created detailed code that checks an integer for divisibility by 2, 3, 5, and 7. This is a great, quick preliminary screening to see if an integer is prime or not. Many composite numbers can be identified this way with a call to this method (PrimeChecker, of course). In the future, I’ll combine this with some other tools to determine if any given number is Prime, and if not, I will return its Greatest Prime Factor.

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