for (int d = 3; d <= (int) Math.sqrt(number); d++)
if (number % d == 0)
returnfalse;
returntrue;
}
for (intd = 3; d <= (int)sqrt((double)number); d++)
However since we have already tested for even numbers, i.e. number % 2, we can safely increment the count to d + 2:
for (intd = 3; d <= (int)sqrt((double)number); d = d + 2)
Sieve of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them which is equal to that prime. Simple Version: http://introcs.cs.princeton.edu/java/14array/PrimeSieve.java.html
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
boolean[] isPrime = new boolean[N + 1]; // can be changed to use BitSet for space efficient
for (int i = 2; i <= N; i++) {
isPrime[i] = true;
}
// mark non-primes <= N using Sieve of Eratosthenes
for (int i = 2; i*i <= N; i++) {
// if i is prime, then mark multiples of i as nonprime
// suffices to consider mutiples i, i+1, ..., N/i
if (isPrime[i]) {
for (int j = i; i*j <= N; j++) {
isPrime[i*j] = false;
}
}
}
// count primes
int primes = 0;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) primes++;
}
System.out.println("The number of primes <= " + N + " is " + primes);
}
public class Sieve
{
private BitSet sieve;
private Sieve() {}
private Sieve(int size) {
sieve = new BitSet((size+1)/2);
}
private boolean is_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
return sieve.get((k-3)/2);
}
private void set_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
sieve.set((k-3)/2);
}
public static List<Integer> sieve_of_eratosthenes(int max)
{
Sieve sieve = new Sieve(max + 1); // +1 to include max itself
for (int i = 3; i*i <= max; i += 2) {
if (sieve.is_composite(i))
continue;
// We increment by 2*i to skip even multiples of i
for (int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
sieve.set_composite(multiple_i);
}
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
for (int i = 3; i <= max; i += 2)
if (!sieve.is_composite(i))
primes.add(i);
return primes;
}
}
Sieve of Atkin- Faster but hard to understand http://en.wikipedia.org/wiki/Sieve_of_Atkin the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient sieve of Eratosthenes which does some preliminary work and then marks off multiples of the square of each prime, rather than multiples of the prime itself.
public class AtkinSieve {
public static int[] findPrimes(int arraySize) {
boolean[] isPrime = new boolean[arraySize + 1];
double sqrt = Math.sqrt(arraySize);
for (int x = 1; x <= sqrt; x++) {
for (int y = 1; y <= sqrt; y++) {
int n = 4 * x * x + y * y;
if (n <= arraySize && (n % 12 == 1 || n % 12 == 5)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x + y * y;
if (n <= arraySize && (n % 12 == 7)) {
isPrime[n] = !isPrime[n];
}
n = 3 * x * x - y * y;
if (x > y && (n <= arraySize) && (n % 12 == 11)) {
isPrime[n] = !isPrime[n];
}
}
}
for (int n = 5; n <= sqrt; n++) {
if (isPrime[n]) {
int s = n * n;
for (int k = s; k <= arraySize; k += s) {
isPrime[k] = false;
}
}
}
int[] primes = new int[arraySize];
int found = 0;
if (arraySize > 2) {
primes[found++] = 2;
}
if (arraySize > 3) {
primes[found++] = 3;
}
for (int n = 5; n <= arraySize; n += 2) {
if (isPrime[n]) {
primes[found++] = n;
}
}
return Arrays.copyOf(primes, found);
}
}
Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.
publicclass LevenshteinDistance {privatestaticint minimum(int a, int b, int c){returnMath.min(Math.min(a, b), c);}publicstaticint computeLevenshteinDistance(String str1,String str2){int[][] distance =newint[str1.length()+1][str2.length()+1];for(int i =0; i <= str1.length(); i++)
distance[i][0]= i;for(int j =1; j <= str2.length(); j++)
distance[0][j]= j;for(int i =1; i <= str1.length(); i++)for(int j =1; j <= str2.length(); j++)
distance[i][j]= minimum(
distance[i -1][j]+1,
distance[i][j -1]+1,
distance[i -1][j -1]+((str1.charAt(i -1)== str2.charAt(j -1))?0:1));return distance[str1.length()][str2.length()];}}
Not recursive and faster
publicint LevenshteinDistance (String s0, String s1){int len0 = s0.length()+1;int len1 = s1.length()+1;// the array of distances int[] cost =newint[len0];int[] newcost =newint[len0];// initial cost of skipping prefix in String s0 for(int i =0; i < len0; i++) cost[i]= i;// dynamicaly computing the array of distances // transformation cost for each letter in s1 for(int j =1; j < len1; j++){// initial cost of skipping prefix in String s1
newcost[0]= j;// transformation cost for each letter in s0 for(int i =1; i < len0; i++){// matching current letters in both strings int match =(s0.charAt(i -1)== s1.charAt(j -1))?0:1;// computing cost for each transformation int cost_replace = cost[i -1]+ match;int cost_insert = cost[i]+1;int cost_delete = newcost[i -1]+1;// keep minimum cost
newcost[i]=Math.min(Math.min(cost_insert, cost_delete), cost_replace);}// swap cost/newcost arrays int[] swap = cost; cost = newcost; newcost = swap;}// the distance is the cost for transforming all letters in both strings return cost[len0 -1];}
publicstaticint levenshtein(String s, String t){/* if either string is empty, difference is inserting all chars
* from the other
*/if(s.length()==0)return t.length();if(t.length()==0)return s.length();/* if first letters are the same, the difference is whatever is
* required to edit the rest of the strings
*/if(s.charAt(0)== t.charAt(0))return levenshtein(s.substring(1), t.substring(1));/* else try:
* changing first letter of s to that of t,
* remove first letter of s, or
* remove first letter of t
*/int a = levenshtein(s.substring(1), t.substring(1));int b = levenshtein(s, t.substring(1));int c = levenshtein(s.substring(1), t);if(a > b) a = b;if(a > c) a = c;//any of which is 1 edit plus editing the rest of the stringsreturn a +1;}
privateint[] numbers;
privateint[] helper;
privateint number;
publicvoid sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = newint[number];
mergesort(0, number - 1);
}
privatevoid mergesort(int low, int high) {
// check if low is smaller then high, if not then the array is sortedif (low < high) {
// Get the index of the element which is in the middleint middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
privatevoid merge(int low, int middle, int high) {
// Copy both parts into the helper arrayfor (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back// to the original arraywhile (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target arraywhile (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
}
publicstaticint[]mergeSort(int[] list){if(list.length<=1){return list;}// Split the array in halfint[] first =newint[list.length/2];int[] second =newint[list.length- first.length];
System.arraycopy(list,0, first,0, first.length);
System.arraycopy(list, first.length, second,0, second.length);// Sort each half
mergeSort(first);
mergeSort(second);// Merge the halves together, overwriting the original array
merge(first, second, list);return list;}privatestaticvoidmerge(int[] first,int[] second,int[] result){// Merge both halves into the result array// Next element to consider in the first arrayint iFirst =0;// Next element to consider in the second arrayint iSecond =0;// Next open position in the resultint j =0;// As long as neither iFirst nor iSecond is past the end, move the// smaller element into the result.while(iFirst < first.length&& iSecond < second.length){if(first[iFirst]< second[iSecond]){
result[j]= first[iFirst];
iFirst++;}else{
result[j]= second[iSecond];
iSecond++;}
j++;}// copy what's left
System.arraycopy(first, iFirst, result, j, first.length- iFirst);
System.arraycopy(second, iSecond, result, j, second.length- iSecond);}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); assert isSorted(a); } http://www.sinbadsoft.com/blog/sorting-big-files-using-k-way-merge-sort/ It consists of two steps: first, split the file into small chunks that would fit in memory, load each chunk, sort it, and write it back on disk. Second, perform a k-way merge on all the sorted chunks to get the final result. External Merge Sort https://code.google.com/p/externalsortinginjava/source/browse/trunk/src/main/java/com/google/code/externalsorting/ExternalSort.java http://exceptional-code.blogspot.com/2011/07/external-sorting-for-sorting-large.html 1. Start reading the input file from the beginning. 2. Read M (or less if number of entries remaining in the file is less than M) numbers from the file and store it into a temp buffer. 3. Sort (using any good sorting method - Quicksort, for example) the numbers in the buffer stored in step 2. 4. Create a temp file in disk and write out the sorted numbers from step 3 to this temp file. Save the name of the temp file. 5. Repeat step 2 to 4 until all numbers from the input file has been read, sorted, and written out to temp files. 6. Open all the temp files (and set the read pointer to the beginning of the files). 7. Find the minimum number from the set of numbers currently pointed to by the file read pointer. 8. Write the number to disk. (To increase efficiency you could write the number to a buffer first and then flush the buffer out to disk when the buffer is full. But modern I/O libraries should be doing this anyway for you). 9. Read another number from the file that contained the minimum number at step 7. 10. Repeat step 7 to 9 until all numbers from all the temp files have been processed, merged, and written out to disk Mergesort using Fork/Join Framework http://www.java-allandsundry.com/2012/08/mergesort-using-forkjoin-framework.html http://www.oracle.com/technetwork/articles/java/fork-join-422606.html https://github.com/cowtowncoder/java-merge-sort
// choose smaller of the smallest in the three ranges
while((i < mid1) && (j < mid2) && (k < high))
{
if(gArray[i].compareTo(gArray[j]) < 0)
{
if(gArray[i].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
else
{
if(gArray[j].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
}
// case where first and second ranges have
// remaining values
while((i < mid1) && (j < mid2))
{
if(gArray[i].compareTo(gArray[j]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[j++];
}
// case where second and third ranges have
// remaining values
while((j < mid2) && (k < high))
{
if(gArray[j].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[j++];
else
destArray[l++] = gArray[k++];
}
// case where first and third ranges have
// remaining values
while((i < mid1) && (k < high))
{
if(gArray[i].compareTo(gArray[k]) < 0)
destArray[l++] = gArray[i++];
else
destArray[l++] = gArray[k++];
}
// copy remaining values from the first range
while(i < mid1)
destArray[l++] = gArray[i++];
// copy remaining values from the second range
while(j < mid2)
destArray[l++] = gArray[j++];
// copy remaining values from the third range
while(k < high)
destArray[l++] = gArray[k++];
}
Time Complexity: In case of 2-way Merge sort we get the equation: T(n) = 2T(n/2) + O(n) Similarly, in case of 3-way Merge sort we get the equation: T(n) = 3T(n/3) + O(n) By solving it using Master method, we get its complexity as O(n log 3n).. Although time complexity looks less compared to 2 way merge sort, the time taken actually may become higher because number of comparisons in merge function go higher http://www.geeksforgeeks.org/binary-search-preferred-ternary-search/
// We reach here when element is not present in array
return-1;
}
Which of the above two does less comparisons in worst case?
From the first look, it seems the ternary search does less number of comparisons as it makes Log3n recursive calls, but binary search makes Log2n recursive calls. Let us take a closer look.
The following is recursive formula for counting comparisons in worst case of Binary Search.
T(n) = T(n/2) + 2, T(1) = 1
The following is recursive formula for counting comparisons in worst case of Ternary Search.
T(n) = T(n/3) + 4, T(1) = 1
In binary search, there are 2Log2n + 1 comparisons in worst case. In ternary search, there are 4Log3n + 1 comparisons in worst case.
Time Complexity for Binary search = 2clog2n + O(1)
Time Complexity for Ternary search = 4clog3n + O(1)
Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.
Mergesort, if implemented to create arrays in the recursive calls, will create many of them, but they won't coexist at the same time. In every recursive call you create an array (or 2 depending on an implementation) for merging and they take no more than O(n) space, and then when the merging is done, these arrays are deleted and some new ones will be created after a moment in some other recursive call. If you counted how much space all the arrays that ever have been created took, it'd be O(n log n), but you don't need to care about this information - you don't need more than O(n) space, because when you need to create an array, all the other ones don't longer exist and don't occupy any memory. Note that you can simply declare 2 - or 3 - arrays in the beginning, each the length of n, and then store the sequence in one of them, while using the other for merging, it will improve the performance as well as show you beyond doubt there's no need for more than O(n) of memory.
