Truncatable primes: Difference between revisions
Content deleted Content added
m sort |
Added Java Implementation. |
||
Line 321: | Line 321: | ||
>./ step&digits^:5 seed NB. right truncatable |
>./ step&digits^:5 seed NB. right truncatable |
||
739399</lang> |
739399</lang> |
||
=={{header|Java}}== |
|||
<lang Java> |
|||
import java.util.BitSet; |
|||
public class Main { |
|||
public static void main(String[] args){ |
|||
final int MAX = 1000000; |
|||
//Sieve of Eratosthenes (using BitSet only for odd numbers) |
|||
BitSet primeList = new BitSet(MAX>>1); |
|||
primeList.set(0,primeList.size(),true); |
|||
int sqroot = (int) Math.sqrt(MAX); |
|||
primeList.clear(0); |
|||
for(int num = 3; num <= sqroot; num+=2) |
|||
{ |
|||
if( primeList.get(num >> 1) ) |
|||
{ |
|||
int inc = num << 1; |
|||
for(int factor = num * num; factor < MAX; factor += inc) |
|||
{ |
|||
//if( ((factor) & 1) == 1) |
|||
//{ |
|||
primeList.clear(factor >> 1); |
|||
//} |
|||
} |
|||
} |
|||
} |
|||
//Sieve ends... |
|||
//Find Largest Truncable Prime. (so we start from 1000000 - 1 |
|||
int rightTrunc = -1, leftTrunc = -1; |
|||
for(int prime = (MAX - 1) | 1; prime >= 3; prime -= 2) |
|||
{ |
|||
if(primeList.get(prime>>1)) |
|||
{ |
|||
//Already found Right Truncable Prime? |
|||
if(rightTrunc == -1) |
|||
{ |
|||
int right = prime; |
|||
while(right > 0 && primeList.get(right >> 1)) right /= 10; |
|||
if(right == 0) rightTrunc = prime; |
|||
} |
|||
//Already found Left Truncable Prime? |
|||
if(leftTrunc == -1 ) |
|||
{ |
|||
//Left Truncation |
|||
String left = String.valueOf(prime); |
|||
if(!left.contains("0")) |
|||
{ |
|||
while( left.length() > 0 ){ |
|||
int iLeft = Integer.parseInt(left); |
|||
if(!primeList.get( iLeft >> 1)) break; |
|||
left = left.substring(1); |
|||
} |
|||
if(left.length() == 0) leftTrunc = prime; |
|||
} |
|||
} |
|||
if(leftTrunc != -1 && rightTrunc != -1) //Found both? then Stop loop |
|||
{ |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
System.out.println("Left Truncable : " + leftTrunc); |
|||
System.out.println("Right Truncable : " + rightTrunc); |
|||
} |
|||
} |
|||
</lang> |
|||
Output : |
|||
<pre> |
|||
Left Truncable : 998443 |
|||
Right Truncable : 796339 |
|||
</pre> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
<lang lua>max_number = 1000000 |
<lang lua>max_number = 1000000 |