Checking for Palindromes and Primes
Posted by Jonathan Ng | Filed under Technical
What’s a palindrome you say? From wikipedia:
A palindrome is a word, phrase, number or other sequence of units (such as a strand of DNA) that has the property of reading the same in either direction (the adjustment of punctuation and spaces between words is generally permitted).
Examples of palindromes: “hannah”. You reverse it, you get “hannah” also. So what we’re required to do (for Data Structures and Algorithm), is to read a string and check if it’s a palindrome. I found 3 ways to do it (hey, that’s what algorithm is all about):
The first way, which I think is the quickest method, compares character for character, and returns when a match isn’t found. In Java, something like 5 / 2 returns 2. Note: assume input is the user’s input string.
int i = 0, j = input.length() - 1;
while (j >= (input.length() / 2)) {
System.out.println(input.charAt(i) + " " + input.charAt(j) );
if (input.charAt(i) != input.charAt(j)) {
System.out.println("Not palindrome");
return;
}
i++; j--;
}
System.out.println("Is palindrome");
Ah, then Denis pointed out that the question required us to actually display the reversed string. Easy, some slight modifications to the code above, and we have:
int i = 0, j = input.length() - 1;
boolean isPal = true;
while (j >= 0) {
System.out.print(input.charAt(j));
if (input.charAt(i) != input.charAt(j)) {
isPal = false;
}
i++; j--;
}
if (isPal) {
System.out.println("\nIs palindrome");
} else {
System.out.println("\nNot palindrome");
}
There’s another way, but very simliar to the above, that uses more of the Java library. I’ve posted the codes (for all 3 methods) here.
Finding Primes
Incidentally, the first question for my practical was write something that finds primes in the range of 1-100. I used the word “incidentally”, because I already did this in the last practical, where my lecturer was teaching boring crap like classes. It’s just some simple use of nested loops, and quite frankly, this is the kind of questions that should be included when we were learning C. I mean, it’s not enough for students to use loops for crap like totalling some number that doesn’t make sense or drawing out patterns made of characters.
So, back to primes. In the last practical, I was dead bored, so I did the script. Heck, I even used longs for the loop counters. It was kinda fun looking at the script, taking nearly half a minute just to fine the next prime (about 7 digits long). Oh, the script was the no brainer type: say we wanna know if n is a prime, we divide n with every other number (except for even numbers) smaller than it to see if there’s no remainder.
I thought there must be some better and faster way to do so. In fact, there was! There’s this sieve of Eratosthenes, which I just absolutely admire. It’s so simple and elegant. Come to think of it, some serious thinking will tell you that multiples of primes, are not prime numbers. There’s an animation that shows how it works too. A faster algorithm, is the sieve of Atkin, which you’ll have to be a mathematician to comprehend. It’s called a sieve because you’ve got like a list of numbers, then you filter out those numbers that aren’t primes.
The .java file for the prime finder (using Eratosthenes) is here. Funny thing was, my lecturer wasn’t aware of such a sieve. Eratosthenes is an ancient Greek mathematician. The algorithm isn’t anything new..
Tags: algorithm
2 Responses to “Checking for Palindromes and Primes”
-
Ben Says:
November 1st, 2006 at 4:51 pmWhy don’t you try implementing the sieve of Atin’s?
-
Jonathan Ng Says:
November 1st, 2006 at 5:48 pmHave to seen the sieve of Atkins?? It’s so blardy complicated.. I will just end up writting a program that does as the formula says, with no understanding of the formula at all.. besides, dont you think I should be moving to other algos?
