Solved

# Need help with functions and prime numbers!

Posted on 2003-02-18
Medium Priority
263 Views
I need help writing a function to determine if a number is prime. I need to include this function in a program that takes a number entered by the user and prints whether or not the number is prime.

The second part is that I need to make a program that determines and prints all the prime numbers between 1 & 10, 000.

If you could help me understand that would be great. Thank you very much for helping

0
Question by:alxnder

LVL 8

Expert Comment

ID: 7980177
ok as per the policy that we follow here .. we cant/wont .. ( most of us) give u full source code ..)
here is how i can help u with some hints

going by the most basic and efficient definition of prime numbers
a number is prime when u cannot divide it completely with any other prime numbers less than itself
so starting with  2
take each number  starting from 3.
maintain a list of known prime numbers ( in an array.)
for all prime numbers which are less than square root of the number .. try division ..  if the division fails for all prime numbers less than the square root ..
then the number is declared prime and it is inserted in the array of prime numbers..
and increase the prime-number count.
0

LVL 8

Expert Comment

ID: 7980187
and if u are given arbitrary number and want to check its primeness .. and if u dont have list of existing prime numbers .. then crude way is to

start from 2
increase divisor till sqrt(number)
and try division test.
if all division fails ( u get some remainder always)
then the number on ur hand is prime number
0

Accepted Solution

chirilabogdan earned 200 total points
ID: 7980188
Here is the program that you need.
The ideea is that a number is prime if is not divided to previous numbers.
So 4 is not prime because 4%2==0
and 5 is prime because 5%2!=0 and 5%3!=0.

#include <stdio.h>

#define MAX_NRPRIME 1000 //this will tell you how many prime nubers you will get.

int NrPrime[MAX_NRPRIME], index;

static void initNrPrime(void)
{
NrPrime[0] = 1;
NrPrime[1] = 2;
index = 1;
}

static int getNrPrime(
int startNr)
{
int prim=0;

for(int i = 1; i <= index; i++) {
if(startNr%NrPrime[i] != 0)
prim+=1;
}
if(prim == index)
return startNr;
return 0;
}

static void printNrPrime()
{
for(int i = 0; i < MAX_NRPRIME; i++) {
printf("\t%6d", NrPrime[i]);
}
}

main()
{
int i,temp;

initNrPrime();
for (; index < MAX_NRPRIME; ) {
i=1;
do {
temp = getNrPrime(NrPrime[index]+i);
i++;

} while (temp == 0);
NrPrime[++index] = temp;
}
printNrPrime();
}
0

LVL 2

Expert Comment

ID: 7980189
There are lots of different methodologies for calculating whether or not a number is prime and for extracting the prime numbers from a range.

Here is a link to an essay on how to sieve for prime numbers.  It includes a C program that will locate all the prime numbers within a range.

If this program isn't to your liking, you might want to google on "Eratosthenes Sieve".

Here is the essay:

http://www.fpx.de/fp/Software/Sieve.html

The program itself might take some tweaking to compile on a modern compiler.  I had to add:

#include <stdlib.h>

to the top of the file (to get atol()), and I had to cast the return value of malloc:

zzz = feld = malloc (alloc=(((max-=10000L)>>4)+1L));

to:

zzz = feld = (unsigned char *) malloc (alloc=(((max-=10000L)>>4)+1L));

to get it to compile on g++.

good luck if you have any questions post a follow-up.

0

LVL 2

Expert Comment

ID: 7983792

For generating prime numbers, try the following:

create one loop, go from 1 (current number) to your 10000 (top number)

create a loop inside, go from 2 (loop control variable) to your current number

check if you can modulo (%) the current number by the loop control variable and get 0 remainder for each time...if you don't get a zero and loop up to the current number, you have a prime number.  if any number that comes before it can modulo it and get 0, then it's not prime

this should be easy...2 if statements inside a for loop, inside a while loop...or something like that

you can also use similar logic to determine if a number is prime

0

Author Comment

ID: 7990051
Thank you for helping me out. I appreciate is very much.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
###### Suggested Courses
Course of the Month8 days, 19 hours left to enroll

#### 621 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.