Velocity Reviews > right prime numbers

# right prime numbers

johnmsimon@gmail.com
Guest
Posts: n/a

 11-08-2006
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 <stdio.h>
#include <math.h>

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.

Arthur J. O'Dwyer
Guest
Posts: n/a

 11-08-2006

On Tue, 7 Nov 2006 http://www.velocityreviews.com/forums/(E-Mail Removed) 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 <stdio.h>
> #include <math.h>
>
> int slowPrime(int); //function prototype
>
> int main()
> {
> int x; // loop counter

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

> {
> 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

Eric
Guest
Posts: n/a

 11-08-2006
(E-Mail Removed) 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 <stdio.h>
> #include <math.h>
>
>
> 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 )
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;

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;
}
//--------------------------------------------------------------

Eric
Guest
Posts: n/a

 11-08-2006
Eric wrote:

> (E-Mail Removed) 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 <stdio.h>
>> #include <math.h>
>>
>>
>> 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 )
> 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;
>
> 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;

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;
}

Walter Roberson
Guest
Posts: n/a

 11-08-2006
In article <(E-Mail Removed) .com>,
<(E-Mail Removed)> wrote:

>#include <stdio.h>
>#include <math.h>

>int slowPrime(int); //function prototype

>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

Keith Thompson
Guest
Posts: n/a

 11-08-2006
http://www.velocityreviews.com/forums/(E-Mail Removed)-cnrc.gc.ca (Walter Roberson) writes:
> In article <(E-Mail Removed) .com>,
> <(E-Mail Removed)> wrote:
>
>>#include <stdio.h>
>>#include <math.h>

>
>>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) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Richard Heathfield
Guest
Posts: n/a

 11-08-2006
Keith Thompson said:
> Walter Roberson writes:
>> <(E-Mail Removed)> wrote:

<snip>

>>>int main()

>>
>> If I recall correctly, that is not a valid declaration of main in C99.
>> [But I could be misremembering.]

<snip>

> 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

Nick Keighley
Guest
Posts: n/a

 11-08-2006
(E-Mail Removed) 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 <stdio.h>
> #include <math.h>
>
>
> 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

Richard Heathfield
Guest
Posts: n/a

 11-08-2006
Nick Keighley said:

> (E-Mail Removed) wrote:
>

<snip>
>>
>> int slowPrime(int); //function prototype

>
> useless comment, you never declare this function

But he just did! That *is* a declaration!

<snip>

--
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

CBFalconer
Guest
Posts: n/a

 11-08-2006
Nick Keighley wrote:
> (E-Mail Removed) 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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>