## Monday, November 30, 2015

### Getting the Prime numbers using the Sieve of Eratosthenes method

Hello Guys, today we are going to look the method by which the large number of prime numbers can be calculated.

The definition of the Sieve of Eratosthenes method goes this way:
"Mark the first presence of the number as prime and mark all its multiples as non primes." - Wiki

Looking at the diagram its pretty clear to understand that the first presence of number is considered to be prime and all the multiples of it (increasing order) is marked non prime also, we will check for the prime only if the number is not marked as non prime before, like in case of 6, the number would be marked as non prime before while we run the thing for the number 2 so it is skipped in case of 3.

Now lets see the program as well, running link here

Here is the code:

```import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
public static void main(String[] args) {
int MAX = 1000000;
int T = 0;
boolean isPrime[] = new boolean[MAX];
for(int i=2; i<isPrime.length; i++)
isPrime[i] = true;

int primes[] = new int[MAX];
int p = 0;
for(int i=2;i<MAX;i++){
if(isPrime[i]){
primes[p++] = i;
for(int j=2*i; j<MAX; j+=i)
isPrime[j] = false;
}
}
System.out.println("All your prime numbers are calculated, just for example I am taking out the 10101th prime number");
T = 10101;
System.out.println(primes[T]);
}
}

```

## Friday, November 20, 2015

### Anagram String and its solutions

Hello Friends, today I want to discuss something about the anagram strings.

Now What is an Anagram String?
"An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; for example, the word anagram can be rearranged into nag-a-ram." - Wiki

Now if I understood correctly then in one way or the other we have to use the same letters that are there in first word for exactly the same number of times they appeared in it, for the second word in any order.

Now coming to the solution part. There are many ways of checking the anagram strings.
1. Using the sorting solution
2. Using the prime number solution
Using the Sorting Algorithm:
This is pretty simple way of checking the Anagram Strings. In this we sort both the Strings that we get for being checked as Anagram and then checks that both the results should be identical.

For example:
If I pass 2 strings, say Anagram and Nagaram, then the algo goes like this:
• Checks whether the length of both the strings are same, if not there is no profit in going forward
• Then change strings to lower case/Upper case, to make sure there should not be any difference because of the cases.
• Sorts both the strings in their natural way either increasing or decreasing order
• Then checks whether both the sorted results are identical
Program:

```public class AnagramCheck_Sort{
public static boolean isAnagram(String s1, String s2){
// Early termination check, if strings are of unequal lengths,
// then they cannot be anagrams
if (s1==null || s2==null || s1.length() != s2.length() ) {
return false;
}

char[] c1 = s1.toLowerCase().toCharArray();
char[] c2 = s2.toLowerCase().toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
String sc1 = new String(c1);
String sc2 = new String(c2);
return sc1.equals(sc2);
}
public static void main(String[] args){
System.out.println(isAnagram("Anagram","nagaram"));
}
}```

Using the prime number solution:
This method is like the brute force. Here goes ihe algo:

• Checks whether the length of both the strings are same if not there is no profit in going forward.
• Then makes a map of character and assign 1 unique prime number to it.For instance assign character 'a' the prime number 2, and character 'b' the prime number 3 and so on for all 26 letters.
• then runs the loop and keep on multiplying by the number that each character posses and keep it in a different variable as a product
• At last because all the number were prime in nature and also the product of two unique primes are always unique we end up getting two products which tells us whether the strings are prime or not. If the two products are same then the strings are prime otherwise not
• One point to note that because we are multiplying the numbers the variable should be of big datatype.
Program:
Here is running version : link

```class AnagramCheck_Sort{
public static boolean isAnagram(String s1, String s2){
// Early termination check, if strings are of unequal lengths,
// then they cannot be anagrams
if (s1==null || s2==null || s1.length() != s2.length() ) {
return false;
}
s1=s1.toLowerCase();s2=s2.toLowerCase();
Integer p1 = 1; Integer p2 = 1;
for(int i=0, len=s1.length(); i!=len; i++){
char c1 = s1.charAt(i);char c2 = s2.charAt(i);
p1 = p1 * primesMap.get(c1);p2 = p2 * primesMap.get(c2);
}

return p1.equals(p2);
}
public static void main(String[] args){
primesMap.put('a',2);primesMap.put('b',3);primesMap.put('c',5);primesMap.put('d',7);primesMap.put('e',11);primesMap.put('f',13);
primesMap.put('g',17);primesMap.put('h',19);primesMap.put('i',23);primesMap.put('j',29);primesMap.put('k',31);primesMap.put('l',37);
primesMap.put('m',41);primesMap.put('n',43);primesMap.put('o',47);primesMap.put('p',53);primesMap.put('q',59);primesMap.put('r',61);
primesMap.put('s',67);primesMap.put('t',71);primesMap.put('u',73);primesMap.put('v',79);primesMap.put('w',83);primesMap.put('x',89);
primesMap.put('y',97);primesMap.put('z',101);

System.out.println(isAnagram("Anagram","nagaram"));
}

private static Map<character ,Integer> primesMap = new HashMap<>();
}

```