?
Solved

Need help with functions and prime numbers!

Posted on 2003-02-18
6
Medium Priority
?
262 Views
Last Modified: 2010-04-15
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
Comment
Question by:alxnder
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
6 Comments
 
LVL 8

Expert Comment

by:akshayxx
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

by:akshayxx
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

by:
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 2

Expert Comment

by:grue
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

by:corduroy9
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

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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Suggested Courses

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

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

Join & Ask a Question