Here is the problem statement for problem #51:
By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.
I'm learning C right now, and this solution is my first original program in the language. I'd love any feedback on it, whether its about style, the algorithm, or any language tricks I could have used to save some time(especially if pointers could have come in handy somewhere. I'm coming from Python, and I feel like I'm stuck in that perspective when it comes to types and variables). It's not the most concise thing in the world, but it gets the right answer in about 2 minutes on my machine. Thanks in advance!
#include <stdio.h>
#include <math.h>
int isprime(int num);
long quick_pow10(int power);
/*solve Project Euler problem 51*/
int main()
{
/*length of potential answer(including last digit)*/
int l = 3;
long ans = -1;
/*in binary, which digits we should change(not including
* last digit)*/
unsigned int digs;
/*loop through lengths of test numbers while ans hasn't been found*/
while(ans < 0) {
printf("l = %d\n", l);
/*loop across which digits to replace(last digit is never
* replaced because it must be odd)*/
for(digs=1; (digs<(1 << (l-1))) && (ans < 0); digs++) {
/*digs, but including last digit*/
unsigned int reps = digs << 1;
printf(" reps=%u\n", reps);
int onecount = 0;
int ones[l];
int i;
int bit;
/* value of digits that aren't changed */
long g;
/*count how many digits are going to be changed and record
* which*/
for(i=l - 1; i >= 0; i -= 1) {
bit = (reps >> i) & 1;
if(bit == 1) {
ones[onecount++] = l - 1 - i;
}
}
/*loop through the possible cumulative values for the
* non-replaced digits in the test number*/
for(g = quick_pow10(l-1-onecount) + ((l-1-onecount)>0);
(g < quick_pow10(l-onecount)) && (ans < 0);
g+=2) {
/* test the l-digit number testnum with the
* substitutions at digits listed in 'ones.'
* non substituted digits are in g.*/
int t;
int primecount = 0;
int failcount = 0;
/*digit counter in g, from least significant*/
int gdc = 0;
/*location in testnum, from least significant digit*/
int tni;
long testnum = 0;
long testnumt;
/*put gdigits into correct locations in testnum*/
for(tni=0; tni < l; tni++) {
if(!((reps >> tni) & 1)) {
testnum +=
((g / quick_pow10(gdc++)) % 10) *
quick_pow10(tni);
}
}
/*loop across the members of the family of
* substitutions. Include 0 only if the first digit
* isn't being changed*/
for(t=9; t >= (int)((reps >> (l - 1)) & 1); t--) {
testnumt = testnum;
int k;
/*build the final testnum*/
for(k=0; k < onecount; k++){
testnumt += t * quick_pow10(l - 1 - ones[k]);
}
if(isprime(testnumt)) {
primecount += 1;
}
else {
if((++failcount) >= 3) {
break;
}
}
}
if(primecount >= 8) {
ans = testnumt;
}
}
}
l++;
}
printf("%ld\n", ans);
}
long quick_pow10(int power)
{
static long pow10[11] = {
1, 10, 100, 1000, 10000,
100000, 1000000, 10000000, 100000000, 1000000000, 10000000000
};
return pow10[power];
}
int isprime(int num)
{
if (num <= 1) return 0;
if (num % 2 == 0 && num > 2) return 0;
for(int i = 3; i < num / 2; i+= 2)
{
if (num % i == 0)
return 0;
}
return 1;
}
EDIT: I was looking at the forum(that opens up when you post a solution) and it turns out that everyone was getting much faster speeds than me by looping across the primes instead of all natural numbers. I'm not changing my code, but in case you're interested :.
>this
to> this
. It's a single character edit and I don't have anything else to fix. \$\endgroup\$