# Prime numbers

• 05-13-2002
Lazy Student
Prime numbers
I am required to write a program which writes all the prime numbers between 1 and 10000, my only problem is that I cant find a way to determine the prime numbers from the rest! plz help! im not good at maths!

I wrote the following:

#include <stdio.h>
int prime (int);
int main ()
{
int i;
prime (i);
return 0;
}

int prime (int i)
{
i=1;
while ( i <=1000) {

if ( i % 2 == 1 && i % 3 == 1)
printf ("%d\n",i);
i++;
}
return i;
}
• 05-13-2002
Shiro
I assume you know what a prime number is, from the definition of a prime number it should be quite easy to write an algorithm for that. Unless you're a Real Lazy Student. :D

A little hint:

Code:

```for n = 1 to 10000 do begin     for i = 2 to n - 1         if (n mod i = 0)             n_is_prime = false; end;```
There are more efficient ways, hint: think about how the square root of n could make the algorithm more efficient. But this one is easy to understand, isn't it?
• 05-13-2002
Magos
Plus: All even numbers are divisible by 2.
• 05-13-2002
muttski
• 05-13-2002
quzah
Quote:

Originally posted by Magos
Plus: All even numbers are divisible by 2.
LMAO. Guess what! Every fifth number is divisible by 5!

Quzah.
• 05-13-2002
Lazy Student
Thank you all!
Quote:

no, im not from europe! i wont tell you where im from! :p :p:p
• 05-13-2002
muttski
well, your not from the US (I dont mean that in an ******* kind of way, just the way you did your number 10.000 not 10,000).
• 05-13-2002
Lazy Student
thats because of my stupid keyboard! i cant recognize the comma from the point! :D
• 05-13-2002
Magos
Quote:

Originally posted by quzah

LMAO. Guess what! Every fifth number is divisible by 5!

Quzah.

What I meant was he doesn't have to check divisibility with every number between 1 and sqrt(n), just the uneven ones (except for 2). That cuts the checks by 50% which will make a great difference on huge numbers.
• 05-13-2002
fyodor
Quote:

LMAO. Guess what! Every fifth number is divisible by 5!
only those in the series 0,5,10...:)
• 05-13-2002
muttski
fenix is right, it would be faster.
• 05-13-2002
quzah
> Windows XP consists of 32 bit extensions and a graphical shell
> for a 16 bit patch to an 8 bit operating system originally coded
> for a 4 bit microprocessor, written by a 2 bit company, that
> can't stand 1 bit of competition.

I've heard this before, applied to Win9x. However, this is inaccurate for WinXP. Windows XP is not an extension of an 8 or 16bit OS at all. WinXP is based off of WinNT. Windows NT is NOT a 16bit OS.

Quzah.
• 05-14-2002
dana_h

int number=1;

while(number<=10000){
if (number<test*2)
{
printf("%4d",number);
i++; ref++; test=2;
}
else
if (number%test==0)
{
number++;
test=2;
}
else
test++;
}