palindromic primes
Posted:
Fri Nov 18, 2011 1:43 am
by clrgq
im trying to figure out how to adjust the following code so that instead of listing primes, it only lists palindromic (reads the same from front to back) primes. while i am doing this in the mainframe, this code is c code so im a little baffled if someone can get me on the right track. pasting the code below.
000001 #include <stdio.h>
000002 #include <stdlib.h>
000003 #include <errno.h>
000004 #include <string.h>
000005
000006 FILE *outputFile;
000007 char buffer[81];
000008 int bytesWritten;
000009
000010 main()
000011 {
000012 int isPrime(int);
000013
000014 int i,j;
000015
000016
000017 /*************************************/
000018 /* Open file to write output */
000019 /*************************************/
000020 outputFile = fopen("DD:OUTPUT", "w");
000021 if (outputFile == NULL)
000022 {
000023 printf("open error: %d/%s\n", errno, strerror(errno));
000024 exit(99);
000025 }
000026
000027 /*************************************/
000028 /* Run program */
000029 /*************************************/
000030
000031 for (i=1; i<15000; i++)
000032 {
000033 if (isPrime(i)==1)
000034 {
000035 bytesWritten = sprintf(buffer,"%d is prime!\n",i);
000036 fwrite(buffer, 1, bytesWritten, outputFile);
000037 }
000038 }
000039
000040 /*************************************/
000041 /* Close output file */
000042 /*************************************/
000043 fclose(outputFile);
000044
000045 return 0;
000046 }
000047
000048 int isPrime (int myInt)
000049 {
000050
000051 int loop;
000052
000053 for (loop = 2; loop < myInt/2+1; loop++)
000054 {
000055 if (myInt%loop==0)
000056 return 0;
000057 }
000058 return 1;
000059 }
000060
Re: palindromic primes
Posted:
Fri Nov 18, 2011 1:55 am
by enrico-sorichetti
where do You have issues ...
the logic or the coding ?
Re: palindromic primes
Posted:
Fri Nov 18, 2011 2:33 am
by enrico-sorichetti
very good mood today...
int ispal(char * s)
{
int i,j,l;
l = strlen(s) - 1 ;
for (i=0,j=l;i<j;i++,j--) {
if ( s[i] != s[j] )
return 0 ;
}
return 1;
}
and here is the code used to test
#include <stdio.h>
#include <string.h>
int ispal(char * s)
{
int i,j,l;
l = strlen(s) - 1 ;
for (i=0,j=l;i<j;i++,j--) {
if ( s[i] != s[j] )
return 0 ;
}
return 1;
}
int main()
{
int i,j,k;
char c[9];
for (i=0;i<1000;i++) {
sprintf(c,"%d",i);
if ( ispal(c) )
printf("%d (%d) >%s< \n",i,(int)strlen(c),c );
}
return 0;
}
quick and dirty
and here is the result
0 (1) >0<
1 (1) >1<
2 (1) >2<
3 (1) >3<
4 (1) >4<
5 (1) >5<
6 (1) >6<
7 (1) >7<
8 (1) >8<
9 (1) >9<
11 (2) >11<
22 (2) >22<
33 (2) >33<
44 (2) >44<
55 (2) >55<
66 (2) >66<
77 (2) >77<
88 (2) >88<
99 (2) >99<
101 (3) >101<
111 (3) >111<
121 (3) >121<
131 (3) >131<
141 (3) >141<
151 (3) >151<
161 (3) >161<
171 (3) >171<
181 (3) >181<
191 (3) >191<
202 (3) >202<
212 (3) >212<
222 (3) >222<
232 (3) >232<
242 (3) >242<
252 (3) >252<
262 (3) >262<
272 (3) >272<
282 (3) >282<
292 (3) >292<
303 (3) >303<
313 (3) >313<
323 (3) >323<
333 (3) >333<
343 (3) >343<
353 (3) >353<
363 (3) >363<
373 (3) >373<
383 (3) >383<
393 (3) >393<
404 (3) >404<
414 (3) >414<
424 (3) >424<
434 (3) >434<
444 (3) >444<
454 (3) >454<
464 (3) >464<
474 (3) >474<
484 (3) >484<
494 (3) >494<
505 (3) >505<
515 (3) >515<
525 (3) >525<
535 (3) >535<
545 (3) >545<
555 (3) >555<
565 (3) >565<
575 (3) >575<
585 (3) >585<
595 (3) >595<
606 (3) >606<
616 (3) >616<
626 (3) >626<
636 (3) >636<
646 (3) >646<
656 (3) >656<
666 (3) >666<
676 (3) >676<
686 (3) >686<
696 (3) >696<
707 (3) >707<
717 (3) >717<
727 (3) >727<
737 (3) >737<
747 (3) >747<
757 (3) >757<
767 (3) >767<
777 (3) >777<
787 (3) >787<
797 (3) >797<
808 (3) >808<
818 (3) >818<
828 (3) >828<
838 (3) >838<
848 (3) >848<
858 (3) >858<
868 (3) >868<
878 (3) >878<
888 (3) >888<
898 (3) >898<
909 (3) >909<
919 (3) >919<
929 (3) >929<
939 (3) >939<
949 (3) >949<
959 (3) >959<
969 (3) >969<
979 (3) >979<
989 (3) >989<
999 (3) >999<
Re: palindromic primes
Posted:
Fri Nov 18, 2011 6:36 am
by BillyBoyo
clrgq wrote: [...]
000017 /*************************************/
000018 /* Open file to write output */
000019 /*************************************/
[...]
000027 /*************************************/
000028 /* Run program */
000029 /*************************************/
[...]
000040 /*************************************/
000041 /* Close output file */
000042 /*************************************/
[...]
000053 for (loop = 2; loop < myInt/2+1; loop++)
I don't know if you wrote the original. None of the comments are worth anything to anybody.
For the myInt/2+1, I would always prefer parentheses, so I know the precedence as do other human readers, without having to wonder about the compiler's view of things. It is also a little shoddy to "fudge" the terminator value just so one can use a particular operator.
If you are doing this for learning, how about considering other ways than "brute force" to calculate the primes. You don't have to ever divide by a multiple of a prime. To put it another way, can you arrange it to divide in the loop by the primes discovered so far, up to the half way point? Maybe keep some counts of which prime shows a number is not prime. Can be interesting. Maybe research some other ways.
Re: palindromic primes
Posted:
Fri Nov 18, 2011 7:04 am
by clrgq
thanks so much enrico! ill give that a shot. billy i didnt write the original. the challenge that's put to me is to alter the original to find and display only the palindromic primes. i don't know c code but it was part of this particular challenge so i think i understand what you're saying in theory about the brute force method but not sure how to go about it another way.
Re: palindromic primes
Posted:
Fri Nov 18, 2011 11:14 am
by enrico-sorichetti
i don't know c code but it was part of this particular challenge
so You were not asking for help, but for somebody to do something for which You are incompetent
the minimum is that You should share the prize with those who did it on Your behalf
Re: palindromic primes
Posted:
Fri Nov 18, 2011 1:07 pm
by enrico-sorichetti
follow on...
no code optimization will make a bad algorithm good
OK for brute force but...
why in heaven test the even numbers ?
is somebody hoping to make a revolutiary discover in mathematics?
and why in isPrime the limit is number/2+1 instead of sqrt(number) + 1
to check if 999999 is prime it means 500000 divisions instead of 1000
meditate on elementary arithmetic... meditate
Re: palindromic primes
Posted:
Fri Nov 18, 2011 5:24 pm
by BillyBoyo
I guess your task is to "have a bash" at a bit of C code. There are a couple of other things, which you can ignore if you like, but which will help as much as picking up a bit of C, probably even more. The first is how to do a bit of research for something. These days you don't have to go to a library, there's loads of stuff on the internet - but, be aware that although the "brute force" is popular, and works, there is also rubbish out there on the internet. So you have to also judge things, try things, etc. The second is to think about the data: if you were to tabulate the "hits" which show that a particular number is not prime, you'd get to the square-root thing by analysis of the data and observation by wondering "how did I get such big primes without getting to half the size of the number tested".
Learning a bit of C is applicable to C and to learning computer languages. The other stuff is applicable generally. If you can research, understand the data and the problems for a given task and produce solution(s) in pseudo-code, then you are taking a bigger step then just getting a bit of C under your belt.
How to avoid dividing by even numbers other than two? In your loop, do increments of two. Leaves you with one thing to think about. Another is, why divide by all those multiples of three? Or four? Oh, we don't need four, it is a multiple of two, five then? Six we've dealt with, multiples of seven, eight we've dealt with, nine, 10, 11 is another one we want. Hey, we're getting to that "we only need to test for multiples of primes" thing, aren't we?
The actual code to implement does not matter much. If you get to write it down such that it works, that is fine. Depends on how much time you have, but it is time well spent, even if you never come across another problem that is directly mathematical. Thinking about the data is a very useful skill in this profession, as is research, finding out about stuff.
Re: palindromic primes
Posted:
Fri Nov 18, 2011 5:29 pm
by Akatsukami
'Fess up. You're intending to submit this to the IOCCC, aren't you,
clrgq?
Re: palindromic primes
Posted:
Fri Nov 18, 2011 5:54 pm
by BillyBoyo
There's a thought. I could set up one of those for Cobol. I could call it the IOC.... rats.