Rosetta Code

Truncatable primes: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|C}}: replace code: number method; non-portable function; speed
Line 155:
 
=={{header|C}}==
<lang C>#include <stdio.h>
#include <stringstdlib.h>
#include <stdlibstring.h>
#include<math.h>
 
#define MAX_PRIME 1000000
int isprime(int n){▼
char s[32]*primes;▼
int isprm[]={0,0,1,1,0,1,0,1,0,0};
int a=7,hn_primes;
if(n<10)return isprm[n];▼
if(!(n&1)||!(n%3))return 0;▼
h=sqrt(n)+3;
while(a<h){▼
if(!(n%a)||!(n%(a-2)))return 0;
a+=6;
}▼
return 1;▼
}▼
 
/* Sieve. If we were to handle 10^9 range, use bit field. Regardless,
void leftTrunc(char*s,int l){
* if a large amount of prime numbers need to be tested, sieve is fast.
memmove(s,s+1,l);
*/
void init_primes()
{
int j;
primes = malloc(sizeof(char) * MAX_PRIME);
memset(primes, 1, MAX_PRIME);
primes[0] = primes[1] = 0;
int i = 2;
while (i * i < MAX_PRIME) {
for (j = i * 2; j < MAX_PRIME; j += i)
primes[j] = 0;
while (++i < MAX_PRIME && !primes[i]);
▲ }
}
 
voidint rightTruncleft_trunc(char*s,int ln){
{
s[l-1]=0;
int tens = 1;
}
while (tens < n) tens *= 10;
 
▲ while (a<hn) {
int isTruncPrime(int n,void(*func)(char*,int)){
▲ if (!(primes[n&1)||!(n%3)]) return 0;
▲ char s[32];
tens /= 10;
while(isprime(n)){▼
▲ if (n <10 tens) return isprm[n]0;
ltoa(n,s,10);
n %= tens;
if(strchr(s,'0'))break;
▲ }
func(s,strlen(s));
if(!(n=atol(s))) return 1;
}
return 0;▼
}
 
▲int isprimeright_trunc(int n){
void getHiTruncPrime(int n,void(*func)(char*,int)){
{
while(n--){
▲ while(isprime (n)) {
if(isTruncPrime(n,func)){
if (!primes[n]) return 0;
printf("%d\n",n);
n /= break10;
}
▲ return 1;
}
}
 
int main(){
{
puts("Highest left- and right-truncatable primes under 1e6:");
int n;
getHiTruncPrime(1000000,leftTrunc);
int max_left = 0, max_right = 0;
getHiTruncPrime(1000000,rightTrunc);
init_primes();
puts("Press Enter");
 
getchar();
for (n = MAX_PRIME - 1; !max_left; n -= 2)
return 0;
if (left_trunc(n)) max_left = n;
}</lang>
 
Output:
for (n = MAX_PRIME - 1; !max_right; n -= 2)
<pre>Highest left- and right-truncatable primes under 1e6:
if (right_trunc(n)) max_right = n;
998443
 
739399
printf("Left: %d; right: %d\n", max_left, max_right);
Press Enter</pre>
▲ return 0;
}</lang>output<lang>Left: 998443; right: 739399</lang>
 
=={{header|C sharp|C#}}==
Retrieved from "https://rosettacode.org/wiki/Truncatable_primes"