Circular primes: Difference between revisions
→{{header|Wren}}: Added embedded version.
(→{{header|Wren}}: Oops.) |
(→{{header|Wren}}: Added embedded version.) |
||
Line 2,405:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
===Wren-cli===
Second part is very slow - over 37 minutes to find all four.
<lang ecmascript>import "/math" for Int
Line 2,480 ⟶ 2,482:
The next 4 circular primes, in repunit format, are:
[R(19), R(23), R(317), R(1031)]
</pre>
<br>
===Embedded===
{{libheader|GMP}}
A massive speed-up, of course, when GMP is plugged in for the 'probably prime' calculations. Around 11.5 minutes including the stretch goal.
<lang ecmascript>/* circular_primes_embedded.wren */
import "./math" for Int
import "./fmt" for Fmt
foreign class Mpz {
construct init() {}
foreign setString(str, base)
foreign probPrime(reps)
}
var circs = []
var isCircular = Fn.new { |n|
var nn = n
var pow = 1 // will eventually contain 10 ^ d where d is number of digits in n
while (nn > 0) {
pow = pow * 10
nn = (nn/10).floor
}
nn = n
while (true) {
nn = nn * 10
var f = (nn/pow).floor // first digit
nn = nn + f * (1 - pow)
if (circs.contains(nn)) return false
if (nn == n) break
if (!Int.isPrime(nn)) return false
}
return true
}
System.print("The first 19 circular primes are:")
var digits = [1, 3, 7, 9]
var q = [1, 2, 3, 5, 7, 9] // queue the numbers to be examined
var fq = [1, 2, 3, 5, 7, 9] // also queue the corresponding first digits
var count = 0
while (true) {
var f = q[0] // peek first element
var fd = fq[0] // peek first digit
if (Int.isPrime(f) && isCircular.call(f)) {
circs.add(f)
count = count + 1
if (count == 19) break
}
q.removeAt(0) // pop first element
fq.removeAt(0) // ditto for first digit queue
if (f != 2 && f != 5) { // if digits > 1 can't contain a 2 or 5
// add numbers with one more digit to queue
// only numbers whose last digit >= first digit need be added
for (d in digits) {
if (d >= fd) {
q.add(f*10+d)
fq.add(fd)
}
}
}
}
System.print(circs)
System.print("\nThe next 4 circular primes, in repunit format, are:")
count = 0
var rus = []
var primes = Int.primeSieve(10000)
var repunit = Mpz.init()
for (p in primes[3..-1]) {
repunit.setString("1" * p, 10)
if (repunit.probPrime(10) > 0) {
rus.add("R(%(p))")
count = count + 1
if (count == 4) break
}
}
System.print(rus)
System.print("\nThe following repunits are probably circular primes:")
for (i in [5003, 9887, 15073, 25031, 35317]) { //, 49081]) {
repunit.setString("1" * i, 10)
Fmt.print("R($-5d) : $s", i, repunit.probPrime(15) > 0)
}</lang>
<br>
and the C program to embed the above script in:
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include "wren.h"
/* C <=> Wren interface functions */
void C_mpzAllocate(WrenVM* vm) {
mpz_t *pz = (mpz_t*)wrenSetSlotNewForeign(vm, 0, 0, sizeof(mpz_t));
mpz_init(*pz);
}
void C_setString(WrenVM* vm) {
mpz_t *pz = (mpz_t*)wrenGetSlotForeign(vm, 0);
const char *str = wrenGetSlotString(vm, 1);
int base = (int)wrenGetSlotDouble(vm, 2);
mpz_set_str(*pz, str, base);
}
void C_probPrime(WrenVM* vm) {
mpz_t *pz = (mpz_t*)wrenGetSlotForeign(vm, 0);
int reps = (int)wrenGetSlotDouble(vm, 1);
int ret = mpz_probab_prime_p(*pz, reps);
wrenSetSlotDouble(vm, 0, (double)ret);
}
WrenForeignClassMethods bindForeignClass(WrenVM* vm, const char* module, const char* className) {
WrenForeignClassMethods methods;
methods.allocate = NULL;
methods.finalize = NULL;
if (strcmp(module, "main") == 0) {
if (strcmp(className, "Mpz") == 0) {
methods.allocate = C_mpzAllocate;
}
}
return methods;
}
WrenForeignMethodFn bindForeignMethod(
WrenVM* vm,
const char* module,
const char* className,
bool isStatic,
const char* signature) {
if (strcmp(module, "main") == 0) {
if (strcmp(className, "Mpz") == 0) {
if (!isStatic && strcmp(signature, "setString(_,_)") == 0) return C_setString;
if (!isStatic && strcmp(signature, "probPrime(_)") == 0) return C_probPrime;
}
}
return NULL;
}
static void writeFn(WrenVM* vm, const char* text) {
printf("%s", text);
}
void errorFn(WrenVM* vm, WrenErrorType errorType, const char* module, const int line, const char* msg) {
switch (errorType) {
case WREN_ERROR_COMPILE:
printf("[%s line %d] [Error] %s\n", module, line, msg);
break;
case WREN_ERROR_STACK_TRACE:
printf("[%s line %d] in %s\n", module, line, msg);
break;
case WREN_ERROR_RUNTIME:
printf("[Runtime Error] %s\n", msg);
break;
}
}
char *readFile(const char *fileName) {
FILE *f = fopen(fileName, "r");
fseek(f, 0, SEEK_END);
long fsize = ftell(f);
rewind(f);
char *script = malloc(fsize + 1);
fread(script, 1, fsize, f);
fclose(f);
script[fsize] = 0;
return script;
}
static void loadModuleComplete(WrenVM* vm, const char* module, WrenLoadModuleResult result) {
if( result.source) free((void*)result.source);
}
WrenLoadModuleResult loadModule(WrenVM* vm, const char* name) {
WrenLoadModuleResult result = {0};
if (strcmp(name, "random") != 0 && strcmp(name, "meta") != 0) {
result.onComplete = loadModuleComplete;
char fullName[strlen(name) + 6];
strcpy(fullName, name);
strcat(fullName, ".wren");
result.source = readFile(fullName);
}
return result;
}
int main(int argc, char **argv) {
WrenConfiguration config;
wrenInitConfiguration(&config);
config.writeFn = &writeFn;
config.errorFn = &errorFn;
config.bindForeignClassFn = &bindForeignClass;
config.bindForeignMethodFn = &bindForeignMethod;
config.loadModuleFn = &loadModule;
WrenVM* vm = wrenNewVM(&config);
const char* module = "main";
const char* fileName = "circular_primes_embedded.wren";
char *script = readFile(fileName);
WrenInterpretResult result = wrenInterpret(vm, module, script);
switch (result) {
case WREN_RESULT_COMPILE_ERROR:
printf("Compile Error!\n");
break;
case WREN_RESULT_RUNTIME_ERROR:
printf("Runtime Error!\n");
break;
case WREN_RESULT_SUCCESS:
break;
}
wrenFreeVM(vm);
free(script);
return 0;
}</lang>
{{out}}
<pre>
The first 19 circular primes are:
[2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933]
The next 4 circular primes, in repunit format, are:
[R(19), R(23), R(317), R(1031)]
The following repunits are probably circular primes:
R(5003 ) : false
R(9887 ) : false
R(15073) : false
R(25031) : false
R(35317) : false
R(49081) : true
</pre>
| |||