right prime numbers

J

johnmsimon

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

Arthur J. O'Dwyer

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

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
 
E

Eric

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 )
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 = 0; // drop last digit
testNum = strtoull(Prime, NULL, 10);
if(!Prime(testNum)) return false
}
return true;
}
//--------------------------------------------------------------
 
E

Eric

Eric said:
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 )
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 = 0; // drop last digit
testNum = strtoull(Prime, 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 = 0; // drop last digit
testNum = strtoull(Prime, NULL, 10);
if(!IsPrime(testNum)) return false;
}
return true;
}
 
W

Walter Roberson

#include <stdio.h>
#include <math.h>
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.
 
K

Keith Thompson

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.)
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".
 
R

Richard Heathfield

Keith Thompson said:
Walter said:
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.
 
N

Nick Keighley

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
 
R

Richard Heathfield

Nick Keighley said:
(e-mail address removed) wrote:


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
adjust your email clients.
 
D

Default User

CBFalconer said:
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
 
D

Don

#include <stdio.h>

/* 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<n); i++)
r *= _(n,(m<=n)?i*m:0,d-1)|!_(i,1,i);
return r;
}

/*------------------------------------------
Print right primes up to the requested value
--------------------------------------------*/
int main(int argc, char* argv[])
{
for(int n = 2; n < 100000; n++)
printf("%d is%s right prime\n",n, _(n,1,n)?"" : " not");
return 0;
}
 
K

Keith Thompson

Don said:
#include <stdio.h>

/* 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.
 
K

Keith Thompson

Ksitami said:

Please provide context when you post a followup. The context was my
comment:
| 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.

I see no evidence that what the web page describes is what the
original poster had in mind. Since the OP was asked repeatedly what
he meant by "right prime" and never bothered to answer, I suggest that
we not waste any more time trying to answer his original question.

(In fact, the code in the original post appears to deal only with
ordinary primes.)

I suggest the following guideline for this newsgroup. (I intend to
follow it myself; others will do as they like).

If you post a question, someone asks you for a clarification, and you
don't reply, then it's safe to assume that you weren't really
interested in getting an answer, and we needn't waste any further time
until and unless you explain what you meant. (That's a general "you",
not referring to any specific purpose.)

I see a lot of discussions here in which people speculate at great
length about what the OP really meant. If you enjoy such speculation,
that's fine, but I suggest that we're under no obligation to figure
out the meaning of an unclear question if the OP is unwilling to
explain it to us.
 
K

Ksitami

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);
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.
 
J

james of tucson

Keith said:
(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 :)
 
C

CBFalconer

K

Keith Thompson

Ksitami said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top