Monday, June 20, 2011

Fun with Prime numbers

Fun with prime numbers

When I am trying to understand the importance of prime numbers, I am really surprised to know that prime numbers have influance not in just mathamatics and computer science but has influance on nature too.

Periodical cicadas, Magicicada species, such as the 17-year and 13-year "locusts," are the longest-lived cicadas. They emerge during synchronized periods, often in spectacular numbers, every 17th or 13th year, respectively. More details refer: Cicadas and Magicicada .If you observe 13 and 17 both are prime numbers. Glenn Webb : A mathamatician found that periodical cicadas have prime number life cycles to avoid syncronization from predators.
If cicadas reprductive cycles are not follwed prime and lets think it as 12 years and if predators reproduce at 4 then predators will get complete feast as both lifecycles are syncronized. For more details please refer : http://philosci40.unibe.ch/lehre/winter06/wtwg_bio/webb01.pdf

Prime numbers have great infulance on hashing and cryptography.



package blog.prime;

import java.util.List;

public interface PrimeGenerator<T extends Number> {
// Return prime numbers between 'from' to  'upto'
    public List<T> getPrimeNumbersUpto(int from, int upto);
// Return prime numbers between 0 to  'upto'
    public List<T> getPrimeNumbersUpto(int upto);
// Returns fixed size of primes numbers from 0
    public List<T> getPrimeNumbersSet(int size);
// Returns fixed size of primes numbers from int
    public List<T> getPrimeNumbersSet(int from, int size);
//Get near prime
    public T getNextProbablePrime(T val);
//Get previous prime
    public T getPreProbablePrime(T val);
// To checks for prime
    public boolean isPrime(T val);
// Returns next prime near to val
}



package blog.prime;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

@ThreadSafe
public enum IntPrimeGenerator implements PrimeGenerator<Integer>  {
    integerSingletonPrime;

    private final int CACHE_INI_SIZE = 5000;
    private List<Integer> primeCache;
    private final Lock lock;
    private IntPrimeGenerator() {
        lock = new ReentrantLock();
        primeCache = Collections.unmodifiableList
                            (getPrimeNumbersSet(0,CACHE_INI_SIZE));
    }

    @Override
    public List<Integer> getPrimeNumbersUpto(int from, int upto) {
        if(from < upto)
            throw new IllegalStateException("'from' cann't be greater than 'upto'");
        int maxCachePrime =  primeCache.get(CACHE_INI_SIZE);
        if(upto == maxCachePrime) return primeCache;
        if(upto < maxCachePrime) 
            return primeCache.subList(
                primeCache.lastIndexOf(findNextNearPrime(from)),
                primeCache.lastIndexOf(findPreNearPrime(upto)));

        if(upto > maxCachePrime && from < maxCachePrime) 
            return getList(
                primeCache.size(), upto,
                primeCache.subList(
                primeCache.lastIndexOf(findNextNearPrime(from)), upto));
        else 
            return getList(from, upto);
    }

    @Override
    public List<Integer> getPrimeNumbersUpto(int to) {
        return getPrimeNumbersUpto(2,to);
    }

    @Override
    public List<Integer> getPrimeNumbersSet(int size) {
        if(size <= CACHE_INI_SIZE)
            return primeCache.subList(0, size);
        else
            throw new IllegalStateException(
                "IntegerPrime doen't support more than "+CACHE_INI_SIZE+"size");
    }

    @Override
    @jdk7("Coin : Improved type inference for generic instance creation (diamond)") 
    public List<Integer> getPrimeNumbersSet(int from, int size) {
        lock.lock();
        try {
            List<Integer> primes;
            if(primeCache == null) {
                primeCache = new CopyOnWriteArrayList<>();
                primes = primeCache;
        } else {
            primes = new CopyOnWriteArrayList<>();
        }
        while(primes.size() != size) {
            if(isPrime(from)) primes.add(from);   from++;
        }
        return primes;
        } finally {
            lock.unlock();
        }
    }

    @Override
    public boolean isPrime(Integer value) {
        int val = value.intValue();
        if(val == 1) return false;
        if(val == 2 || val == 3) return true;
        //Ignore even numbers
        if((val & 0b0001) == 0) return false;
        //Search in cache.
        if(primeCache.contains(val)) return true;
        if(primeCache.get(primeCache.size()-1) > val) return false;
        int flag=1;
        for(int i=2; i<=Math.sqrt(val); i++) {
            if(primeCache.size() > i) {
                if(val%primeCache.get(flag++) == 0) return false;
            } else {
                if(val%i == 0) return false;
            }
        }
        return true;
    }

    private Integer findNextNearPrime(Integer val) {
        while(true)
            if(isPrime(++val)) return val;
    }

    private Integer findPreNearPrime(Integer val) {
        while(true)
        if(isPrime(--val)) return val;
    }

    private List<Integer> getList(int from, int upto) {
        return getList(from, upto, new ArrayList<Integer>());
    }

    private List<Integer> getList(int from, int upto, List<Integer> primeList) {
        for(int i=from;i<=upto; i++)
            if(isPrime(i)) primeList.add(i);
        return primeList;
    }

    private int getNearInBasePrime(int val) {
        if(val > primeCache.get(CACHE_INI_SIZE-1))
            throw new IllegalStateException("Value is out of scope");
        int left = 0, right = CACHE_INI_SIZE, mid=0;
        while(left != right-1) {
            mid = (left + right) >> 1;
            if(primeCache.get(mid) > val)  right = mid;
            else left = mid;
        }
        return left;
    }
    public Integer getNextProbablePrime(Integer value) {
     int val = value.intValue();
        if(val < 2) return 2;
        if(primeCache.get(CACHE_INI_SIZE-1) > val) {
            int left = getNearInBasePrime(val);
            if(left != CACHE_INI_SIZE)
                return primeCache.get( left + 1);
        }
        return findNextNearPrime(val);
    }
     
    public Integer getPreProbablePrime(Integer value) {
        int val = value.intValue();
        if(val <= 2) throw new IllegalStateException("Not possible");
        if(primeCache.get(CACHE_INI_SIZE-1) > val) {
            if(!primeCache.contains(val)) {
                int left = getNearInBasePrime(val);
                if(left != 0)
                    return primeCache.get(left);
            } 
        }
        return findPreNearPrime(val);
    }
}

@interface ThreadSafe {

}
@interface jdk7 {
String value();
}