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(); } |
Monday, June 20, 2011
Fun with Prime numbers
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment