Rosetta Code

Smarandache prime-digital sequence: Difference between revisions

Page Discussion

Smarandache prime-digital sequence (view source)

Revision as of 13:40, 8 July 2020

1,514 bytes removed ,  3 years ago
C code doesn't use a prime sieve (no benefit in this case)
(Added Rust solution)
(C code doesn't use a prime sieve (no benefit in this case))
Line 179:
=={{header|C}}==
{{trans|C++}}
<lang c>#include <assertstdbool.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
typedef struct bit_array_tag {
uint32_t size;
uint32_t* array;
} bit_array;
 
bool bit_array_create(bit_array* b, uint32_t size) {
uint32_t* array = calloc((size + 31)/32, sizeof(uint32_t));
if (array == NULL)
return false;
b->size = size;
b->array = array;
return true;
}
 
void bit_array_destroy(bit_array* b) {
free(b->array);
b->array = NULL;
}
 
void bit_array_set(bit_array* b, uint32_t index, bool value) {
assert(index < b->size);
uint32_t* p = &b->array[index >> 5];
uint32_t bit = 1 << (index & 31);
if (value)
*p |= bit;
else
*p &= ~bit;
}
 
bool bit_array_get(const bit_array* b, uint32_t index) {
assert(index < b->size);
uint32_t* p = &b->array[index >> 5];
uint32_t bit = 1 << (index & 31);
return (*p & bit) != 0;
}
 
typedef struct sieve_tag {
uint32_t limit;
bit_array not_prime;
} sieve;
 
bool sieve_create(sieve* s, uint32_t limit) {
if (!bit_array_create(&s->not_prime, limit + 1))
return false;
bit_array_set(&s->not_prime, 0, true);
bit_array_set(&s->not_prime, 1, true);
for (uint32_t p = 2; p * p <= limit; ++p) {
if (bit_array_get(&s->not_prime, p) == false) {
for (uint32_t q = p * p; q <= limit; q += p)
bit_array_set(&s->not_prime, q, true);
}
}
s->limit = limit;
return true;
}
 
void sieve_destroy(sieve* s) {
bit_array_destroy(&s->not_prime);
}
 
bool is_prime(const sieve* s, uint32_t n) {
assert(n <= s->limit);
return bit_array_get(&s->not_prime, n) == false;
}
 
uint32_t next_prime_digit_number(uint32_t n) {
Line 262 ⟶ 195:
return 2 + next_prime_digit_number(n/10) * 10;
}
}
 
bool is_prime(uint32_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (uint32_t p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
 
int main() {
const uint32_t limit = 10000000;
sieve s = { 0 };
if (!sieve_create(&s, limit)) {
fprintf(stderr, "Out of memory\n");
return 1;
}
uint32_t n = 0, n1 = 0, n2 = 0, n3 = 0;
printf("First 25 SPDS primes:\n");
for (int i = 0; n < limit; ) {
n = next_prime_digit_number(n);
if (!is_prime(n >= limit))
breakcontinue;
if (is_prime(&s,i n)< 25) {
if (i <> 250) {
if printf(i >", 0");
printf("%u", "n);
printf("%u", n);
}
else if (i == 25)
printf("\n");
++i;
if (i == 100)
n1 = n;
else if (i == 1000)
n2 = n;
n3 = n;
}
else if (i == 25)
printf("\n");
++i;
if (i == 100)
n1 = n;
else if (i == 1000)
n2 = n;
n3 = n;
}
sieve_destroy(&s);
printf("Hundredth SPDS prime: %u\n", n1);
printf("Thousandth SPDS prime: %u\n", n2);
Simonjsaunders
1,777

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/290858"