425,992 Members | 934 Online
Need help? Post your question and get tips & solutions from a community of 425,992 IT Pros & Developers. It's quick & easy.

# right prime numbers

 P: n/a i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is complicated. we are on a functions chapter. i am usung the square root to find the prime. so far i have accomplished this but i cant fgure how to divide this by ten so i can find the right prime. i am using c. #include #include int slowPrime(int); //function prototype int main() { int x; // loop counter int count = 0; // total numbers of prime found long prime; printf_s("The prime numbers from 1 to 10000 are:\n" ); for ( x = 2; x <= 2147483647 ; x++ ) { if ( Prime( x ) ) { ++count; // count and print prime //printf_s("%10d", x ); if ( count % 10 == 0 ) // new line after 10 values diplayed printf_s( "\n" ); } // end for } // end if printf_s("%d prime numbers were found\n", count); return 0; // indicate successful termination } // end main int isRightPrime( int n ) // slow prime returns 1 if n is prime { int i; // loop counter for ( i = 2; i <= (int)sqrt (n); i++ ) { if ( n % i == 0 ) return 0; } // end for return 1; } // end function prime i know this can not be as complicated as i have made it. Nov 8 '06 #1
25 Replies

 P: n/a On Tue, 7 Nov 2006 jo********@gmail.com wrote: > i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is complicated. we are on a functions chapter. i am usung the square root to find the prime. so far i have accomplished this but i cant fgure how to divide this by ten so i can find the right prime. i am using c. Is "right prime" different from "prime"? #include #include int slowPrime(int); //function prototype int main() { int x; // loop counter Your indentation got messed up by your newsreader; I've restored proper indentation below. int count = 0; // total numbers of prime found long prime; printf_s("The prime numbers from 1 to 10000 are:\n" ); 'printf_s' should be 'printf', of course. for ( x = 2; x <= 2147483647 ; x++ ) When will this loop terminate if INT_MAX (the maximum possible value of an 'int') is 32767? What if INT_MAX is 2147483647? Remember, all ints are by definition at most INT_MAX --- there are no ints greater than INT_MAX. Also, you might consider how many even primes there are, and then modify your program accordingly. { if (Prime(x)) { I haven't seen a prototype for 'Prime' yet. You should put declarations for all your functions (except, usually, 'main') at the top of your program, or at least somewhere prior to their first use. ++count; // count and print prime //printf_s("%10d", x ); if (count % 10 == 0) // new line after 10 values diplayed printf_s( "\n" ); } // end for } // end if printf_s("%d prime numbers were found\n", count); return 0; // indicate successful termination } // end main int isRightPrime( int n ) // slow prime returns 1 if n is prime { int i; // loop counter for (i=2; i <= (int)sqrt(n); i++) { As before, consider that there is only one even prime. Look up the "Sieve of Eratosthenes", if you haven't yet. Also notice that "i <= (int)sqrt(n)" is basically testing the same thing as "i*i <= n". Which of those two expressions do you think would execute faster on a real-world computer? if (n % i == 0) return 0; } // end for return 1; } // end function prime Where's the definition of 'Prime'? I also notice that the function 'isRightPrime' was never used. i know this can not be as complicated as i have made it. Modulo all those elementary errors and bugs, you've got the basic naive algorithm for prime testing. There's nothing wrong with using it for tiny numbers (say, numbers less than 2^32). For bigger numbers, there are faster algorithms. -Arthur Nov 8 '06 #2

 P: n/a jo********@gmail.com wrote: i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is complicated. we are on a functions chapter. i am usung the square root to find the prime. so far i have accomplished this but i cant fgure how to divide this by ten so i can find the right prime. i am using c. #include #include int slowPrime(int); //function prototype int main() { int x; // loop counter int count = 0; // total numbers of prime found long prime; printf_s("The prime numbers from 1 to 10000 are:\n" ); for ( x = 2; x <= 2147483647 ; x++ ) { if ( Prime( x ) ) { ++count; // count and print prime //printf_s("%10d", x ); if ( count % 10 == 0 ) // new line after 10 values diplayed printf_s( "\n" ); } // end for } // end if printf_s("%d prime numbers were found\n", count); return 0; // indicate successful termination } // end main int isRightPrime( int n ) // slow prime returns 1 if n is prime { int i; // loop counter for ( i = 2; i <= (int)sqrt (n); i++ ) { if ( n % i == 0 ) return 0; } // end for return 1; } // end function prime i know this can not be as complicated as i have made it. True, and I'm still a little unclear as to your question. But I can offer a couple of things that might be usefull. 1: for ( x = 2; x <= 2147483647 ; x++ ) is wasting cycles checking even numbers for primes. try this for ( x = 3; x <= 2147483647 ; x+=2 ) you already know 2 is prime so do your other stuff on it before the for loop begins 2: Is this the correct definition of a right prime? "if N is prime and all numbers obtained by successively removing the rightmost digits of N are prime then its a "right prime"." based on that here's a fn that should do it (its untested, off the top of my head, so it might be buggy) Eric const int true = 1; const int false = 0; int IsRightPrime(unsigned long long int PrimeNumber) { char Prime[33]; // set this to max digits in PrimeNumber + 1 int i, lastchar; unsigned long long int testNum; sprintf(Prime, "%lld", PrimeNumber) lastchar = strlen(Prime)-1; for(i=lastchar; i>0; i--) { Prime[i] = 0; // drop last digit testNum = strtoull(Prime[i], NULL, 10); if(!Prime(testNum)) return false } return true; } //-------------------------------------------------------------- Nov 8 '06 #3

 P: n/a Eric wrote: jo********@gmail.com wrote: >i need to develop a code that finds a prime right number between 2 and100000. and print one line of text that indicates if the int. is rightprime. i am in beginning programing so complex is complicated. we areon a functions chapter. i am usung the square root to find the prime.so far i have accomplished this but i cant fgure how to divide this byten so i can find the right prime. i am using c. #include #include int slowPrime(int); //function prototypeint main(){int x; // loop counterint count = 0; // total numbers of prime foundlong prime; printf_s("The prime numbers from 1 to 10000 are:\n" ); for ( x = 2; x <= 2147483647 ; x++ ){if ( Prime( x ) ){++count; // count and print prime//printf_s("%10d", x );if ( count % 10 == 0 ) // new line after 10 values diplayedprintf_s( "\n" );} // end for} // end if printf_s("%d prime numbers were found\n", count);return 0; // indicate successful termination} // end mainint isRightPrime( int n ) // slow prime returns 1 if n is prime{int i; // loop counterfor ( i = 2; i <= (int)sqrt (n); i++ ){if ( n % i == 0 )return 0;} // end forreturn 1;} // end function prime i know this can not be as complicated as i have made it. True, and I'm still a little unclear as to your question. But I can offer a couple of things that might be usefull. 1: for ( x = 2; x <= 2147483647 ; x++ ) is wasting cycles checking even numbers for primes. try this for ( x = 3; x <= 2147483647 ; x+=2 ) you already know 2 is prime so do your other stuff on it before the for loop begins 2: Is this the correct definition of a right prime? "if N is prime and all numbers obtained by successively removing the rightmost digits of N are prime then its a "right prime"." based on that here's a fn that should do it (its untested, off the top of my head, so it might be buggy) Eric const int true = 1; const int false = 0; int IsRightPrime(unsigned long long int PrimeNumber) { char Prime[33]; // set this to max digits in PrimeNumber + 1 int i, lastchar; unsigned long long int testNum; sprintf(Prime, "%lld", PrimeNumber) lastchar = strlen(Prime)-1; for(i=lastchar; i>0; i--) { Prime[i] = 0; // drop last digit testNum = strtoull(Prime[i], NULL, 10); if(!Prime(testNum)) return false } return true; } //-------------------------------------------------------------- ahem: (after staring at it a bit after posting...) char Prime[33]; // set this to max digits in PrimeNumber + 1 int i, lastchar; unsigned long long int testNum; sprintf(Prime, "%lld", PrimeNumber); lastchar = strlen(Prime)-1; for(i=lastchar; i>0; i--) { Prime[i] = 0; // drop last digit testNum = strtoull(Prime, NULL, 10); if(!IsPrime(testNum)) return false; } return true; } Nov 8 '06 #4

 P: n/a In article <11**********************@f16g2000cwb.googlegroups .com>, #include #include >int slowPrime(int); //function prototype Your use of // comments indicate that you are using C99. >int main() If I recall correctly, that is not a valid declaration of main in C99. [But I could be misremembering.] Try int main(void) Not that it will likely make any noticable difference, but it will at least fix the language level incompatability. >for ( x = 2; x <= 2147483647 ; x++ ){if ( Prime( x ) ){++count; // count and print prime//printf_s("%10d", x ); You appear to have commented out printing of the primes. And you do not appear to be leaving a space between the primes being printed. -- Is there any thing whereof it may be said, See, this is new? It hath been already of old time, which was before us. -- Ecclesiastes Nov 8 '06 #5

 P: n/a ro******@ibd.nrc-cnrc.gc.ca (Walter Roberson) writes: In article <11**********************@f16g2000cwb.googlegroups .com>, >#include #include >>int slowPrime(int); //function prototype Your use of // comments indicate that you are using C99. Or a compiler that supports // comments as an extension (many of them do). But it's a bad idea to use // comments in code posted to Usenet; line wrapping can easily introduce syntax errors. >>int main() If I recall correctly, that is not a valid declaration of main in C99. [But I could be misremembering.] Try int main(void) Not that it will likely make any noticable difference, but it will at least fix the language level incompatability. I believe "int main()" is valid, but "int main(void)" is preferred. ("int main()" declares main as a function taking an unspecified number and type(s) of arguments, but if it's part of a definition it's ok. But "int main(void)" is more explicit, and there's no good reason not to specify the "void" explicitly.) >>for ( x = 2; x <= 2147483647 ; x++ ){if ( Prime( x ) ){++count; // count and print prime//printf_s("%10d", x ); You appear to have commented out printing of the primes. And you do not appear to be leaving a space between the primes being printed. Using the "%10d" format means there will be spaces between the primes as long as they're less than 10 digits -- assuming that the non-standard (or at least other-standard) "printf_s" behaves like "printf". -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 8 '06 #6

 P: n/a Keith Thompson said: Walter Roberson writes: > >>>int main() If I recall correctly, that is not a valid declaration of main in C99.[But I could be misremembering.] I believe "int main()" is valid, but "int main(void)" is preferred. There is no need for us to recall or believe. We can simply consult the Standard, and then we'll know for sure. See 6.7.5.3, which says in part: "An empty list in a function declarator that is part of a definition of that function specifies that the function has no parameters." Therefore, in a function definition, int main() and int main(void) are equivalent, and therefore a function definition beginning with int main() is well-defined, by the equivalence rule of 5.1.2.2.1(1). -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: normal service will be restored as soon as possible. Please do not adjust your email clients. Nov 8 '06 #7

 P: n/a jo********@gmail.com wrote: i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. what's a "right prime"? i am in beginning programing so complex is complicated. we are on a functions chapter. i am usung the square root to find the prime. ?? so far i have accomplished this but i cant fgure how to divide this by ten so i can find the right prime. i am using c. #include #include int slowPrime(int); //function prototype useless comment, you never declare this function int main() { int x; // loop counter int count = 0; // total numbers of prime found long prime; you never use this printf_s("The prime numbers from 1 to 10000 are:\n" ); what is print_s? You said you were going to print the primes below 100000... for ( x = 2; x <= 2147483647 ; x++ ) 2147483647 != 10000 2147483647 != 100000 { if ( Prime( x ) ) no prototype in scope. No declaration. { ++count; // count and print prime //printf_s("%10d", x ); if ( count % 10 == 0 ) // new line after 10 values diplayed printf_s( "\n" ); } // end for } // end if if you laid your program out correctly you would (a) notice that these comments are incorrect (b) not need them printf_s("%d prime numbers were found\n", count); return 0; // indicate successful termination } // end main int isRightPrime( int n ) // slow prime returns 1 if n is prime this is never called { int i; // loop counter for ( i = 2; i <= (int)sqrt (n); i++ ) { if ( n % i == 0 ) return 0; } // end for return 1; } // end function prime i know this can not be as complicated as i have made it. Now post something that compiles. -- Nick Keighley "There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." -- C.A.R. Hoare Nov 8 '06 #8

 P: n/a Nick Keighley said: jo********@gmail.com wrote: >>int slowPrime(int); //function prototype useless comment, you never declare this function But he just did! That *is* a declaration! -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: normal service will be restored as soon as possible. Please do not adjust your email clients. Nov 8 '06 #9

 P: n/a Nick Keighley wrote: jo********@gmail.com wrote: >i need to develop a code that finds a prime right number between2 and 100000. and print one line of text that indicates if theint. is right prime. what's a "right prime"? By analogy with a right whale, it is slow, fat and blubbery, easy to catch, and an endangered species. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. Nov 8 '06 #10

 P: n/a CBFalconer wrote: Nick Keighley wrote: jo********@gmail.com wrote: i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. what's a "right prime"? By analogy with a right whale, it is slow, fat and blubbery, easy to catch, and an endangered species. And floats after being harpooned. Brian Nov 8 '06 #11

 P: n/a Richard Heathfield wrote: Nick Keighley said: jo********@gmail.com wrote: > int slowPrime(int); //function prototype useless comment, you never declare this function But he just did! That *is* a declaration! I swopped definition and declaration (again). :-( -- Nick Keighley Nov 9 '06 #12

 P: n/a #include /* This program implements a blindingly fast O(n^n) algorithm to find right prime numbers, using an elegant recursive method. It does not use the square root function, which is very slow. */ int _(int n, int m, int d) { int r = m != n; for(int i=0; d && (i

 P: n/a "Don" i need to develop a code that finds a prime right number between 2 and100000. and print one line of text that indicates if the int. is rightprime. i am in beginning programing so complex is complicated. we areon a functions chapter. i am usung the square root to find the prime.so far i have accomplished this but i cant fgure how to divide this byten so i can find the right prime. i am using c.i know this can not be as complicated as i have made it. #include /* This program implements a blindingly fast O(n^n) algorithm to find right prime numbers, using an elegant recursive method. It does not use the square root function, which is very slow. */ [code snipped] Please don't top-post. See the following: http://www.caliburn.nl/topposting.html http://www.cpax.org.uk/prg/writings/topposting.php I still have no idea what a "right prime" number is, as opposed to a prime number. Unless you happen to be familiar with the term, there's not much point in replying until and unless the OP explains what he really means. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 28 '06 #14

 P: n/a Nov 28 '06 #15

 P: n/a "Ksitami" San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 28 '06 #16

 P: n/a function isprime(p:dword):boolean; var i,s:dword; begin result:=false; if p<2 then exit; if p<4 then begin result:=true; exit end; if (p mod 2=0) or (p mod 3=0) then exit; i:=5; s:=round(sqrt(p)); while i<=s do begin if p mod i=0 then exit; i+=2; if p mod i=0 then exit; i+=4 end; result:=true end; const nsp=5; sp:array[1..nsp] of dword=(1,3,5,7,9); procedure x(r:dword); var i:dword; begin if isprime(r) then begin writeln(r:9); for i:=1 to nsp do x(r*10 + sp[i]); end; end; begin l:=0; lt:=0; x(2); writeln(#10); x(3); writeln(#10); x(5); writeln(#10); x(7); writeln(#10); writeln(lt); end. Nov 28 '06 #17

 P: n/a Keith Thompson wrote: (In fact, the code in the original post appears to deal only with ordinary primes.) Well, if you find all the primes you know you have both the right and the wrong ones :-) Nov 28 '06 #18

 P: n/a "Ksitami" San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 28 '06 #19

 P: n/a Keith Thompson function isprime(p:dword):boolean;var i,s:dword; [snip] You posted a program in some language that closely resembles Pascal. This is comp.lang.c. Your article is off-topic and inappriate here. Fumble fingers. I meant "inappropriate", of course. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 28 '06 #20

 P: n/a Ksitami wrote: > http://mathworld.wolfram.com/TruncatablePrime.html Incomprehensible. See below. -- If you want to post a followup via groups.google.com, ensure you quote enough for the article to make sense. Google is only a poor interface to usenet. There is no reason to assume your readers can, or ever will, see any previous articles. More details at: Also see Nov 29 '06 #21

 P: n/a Ksitami wrote: > function isprime(p:dword):boolean; This isn't C. var i,s:dword; dword is undefined. Invalid Pascal. begin result:=false; result is undefined. Invalid Pascal. if p<2 then exit; This isn't even Pascal. if p<4 then begin result:=true; exit end; if (p mod 2=0) or (p mod 3=0) then exit; i:=5; s:=round(sqrt(p)); while i<=s do begin if p mod i=0 then exit; i+=2; if p mod i=0 then exit; i+=4 end; result:=true end; const Nor is this. The const section precedes the var section. nsp=5; sp:array[1..nsp] of dword=(1,3,5,7,9); And this is an abortion. Certainly not legal Pascal nor C > procedure x(r:dword); var i:dword; begin if isprime(r) then begin writeln(r:9); for i:=1 to nsp do x(r*10 + sp[i]); end; end; begin l:=0; lt:=0; x(2); writeln(#10); Illegal Pascal construct. Also illegal C. x(3); writeln(#10); x(5); writeln(#10); x(7); writeln(#10); writeln(lt); end. Epitome of uselessness. -- Chuck F (cbfalconer at maineline dot net) Available for consulting/temporary embedded and systems. Nov 29 '06 #22

 P: n/a /* Right-truncatable primes: A zerofree number n is called right truncatable if n and all numbers obtained by successively removing the rightmost digits are prime. There are exactly 83 right truncatable primes in base 10. The first few are 2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, ... (Sloane's A024770), the largest being the 8-digit number 73939133 (Angell and Godwin 1977). ------------------- Weisstein, Eric W. "Truncatable Prime." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/TruncatablePrime.html */ #include typedef unsigned long int uint; uint isprime(uint p) { if (p<2) return 0; if (p<4) return 1; if (0==p%2 || 0==p%3) return 0; uint i=5; while (i*i <=p ){ if (p%i==0) return 0; i+=2; if (p%i==0) return 0; i+=4; } return 1; } uint sp[]={1,3,5,7,9,0}; uint k=0; void x(uint r){ uint i; if (isprime(r)){ printf("%3d %9d\n", ++k, r); for (i=0; sp[i]!=0; i++) x(r*10 + sp[i]); } } int main(){ x(2); x(3); x(5); x(7); getchar(); return 0; } Nov 29 '06 #23

 P: n/a uint isRTP(uint r) { while (r>0) { if (! isprime(r)) return 0; r/=10; } return 1; } Nov 29 '06 #24

 P: n/a "Ksitami" 0) { if (! isprime(r)) return 0; r/=10; } return 1; } Please provide context when you post a followup. Google Groups formerly had a bug that made this difficult; that bug has been fixed, but San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Nov 29 '06 #25

 P: n/a actually i origionally posted it in trying to fing a right prime which is a number that all the numbers in the numbers is prime. say 573. the 3 5 and 7 are all prime. somehow the number needs to be broken down divisibly by 10 for each character and then checked for prime. simon Keith Thompson wrote: "Ksitami" 0) { if (! isprime(r)) return 0; r/=10; } return 1; } Please provide context when you post a followup. Google Groups formerly had a bug that made this difficult; that bug has been fixed, but San Diego Supercomputer Center <* We must do something. This is something. Therefore, we must do this. Dec 9 '06 #26

### This discussion thread is closed

Replies have been disabled for this discussion.