Thread: Using Prime Numbers to Check if Two Words are Anagrams

1. Using Prime Numbers to Check if Two Words are Anagrams

Not too long ago I came across a neat (but inefficient) algorithm that uses prime numbers to determine if two words are anagrams. The way it works is simple:

1. Map each of the 26 English letters to a unique prime number.
2. Multiply the characters of each word.
3. Since every integer is either a prime itself OR a unique product of primes, two words are anagrams if their products are the same.

Example:

Map A -> 2
Map E -> 3
Map R -> 5

Let's check the two words ear and era:

For f("ear") = 3 * 2 * 5 = 30, and for f("era") = 3 * 5 * 2 = 30. Since the product is the same, the two words are anagrams. You could try less obvious examples and it will work just the same way.

Here's my version in Java with more test cases, using my own prime generator.

Obviously there are more efficient ways of finding anagrams, but I never thought you could use primes to actually make it happen. Regular numbers work on some words but will often give you the wrong answer. With prime numbers, the 'fundamental theorem of arithmetic' necessitates that every time we have an equal product, what we have must be an anagram.

Pretty cool!

2. That is pretty cool.

3. Order of Kilopi
Join Date
Jun 2006
Posts
4,692

Mathematical Games

Without half trying, I can think of a cryptographic application.

4. Jon Bentley, in Programming Pearls did this by reading the dictionary file, then signing each word. See https://tfetimes.com/wp-content/uplo...nd.pdf#page274

I'll post my version over the weekend.
Last edited by swampyankee; 2018-Feb-06 at 09:02 PM.

5. Originally Posted by John Mendenhall
Without half trying, I can think of a cryptographic application.
As long as you don't mind that every word in the decrypted text is an anagram of the original!

But many encryption techniques do use the fact that it is hard to find the prime factors of large numbers so you may be on to something

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•