?
Solved

problem coding primality program

Posted on 1998-09-08
5
Medium Priority
?
258 Views
Last Modified: 2010-04-10
I need to write a program that tests for primality of a number without using any functions except for those that are
built in such as sqrt. Any help would be appreciated. Thanks in advance
0
Comment
Question by:BJR
[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
  • 3
  • 2
5 Comments
 
LVL 1

Accepted Solution

by:
mlaiosa earned 200 total points
ID: 1172303
Well, if you want to really chicken out, I wrote such a progam about 8 months ago, I'd send you the source, but otherwise, here are some tips:

Consider:
 All composite numbers have a factor equal or less than it's square root

1: therefore, if you are testing for the primeness of 'n', you need to see if all the numbers between 1 and sqrt(n) are a factor of n.

2: if you determin that 'a' is not a factor of n, then you do not need to check any multiple of 'a'

3: 'a' is a factor of 'n' if:  n%a==0  or correctly mathmaticaly notated: a n(mod a) = 0 -> 'a' is a factor of 'n'

we will take advantage of statement (2) only in that if n is not even, it has no even factors

so, this is what you might do:

long int max,n,f;

void main ()
{
 cin >> n;            //get a number
 max=sqrt(n)+1;   //determine how far we need to go to prove primness.
                          //add 1 to compensate for integer math truncation
 if (n % 2 == 0) //if it is divisable by 2
  {
   cout << "\nnot prime\n";   //then it is defenatly not prime
   return;
  }
 else
 {
  for (f=3; f < max; f+=2)     //start at 3, go up by 2 (hitting the odd numbers)
   if (n%f == 0)  //if 'f' is a factor of 'n'
    {
     cout << "\nnot prime\n";  //it's not prime
     return;
    }
 }
 //we've tried all the possibilities, so it must be prime
 cout << "\nPrime!\n";
 return;
}

Well, that has some buggs (it will tell you that 2 is not prime, for example) but its a big start.  If you want to see the source for the one I wrote a while (it's quite nice) just say so.  Also, to prove the primeness of really large numbers, you might consider useing 'long unsigned int' or if your compiler supports it 'long long unsigned int'
0
 

Author Comment

by:BJR
ID: 1172304
Thanks mlaiosa
I still would be happy to receive your source code for the problem. I have many nested else if statements to get around some of the bugs you've mentioned, such as not including 2 as the first prime number. Where I run into trouble is in my
for (i = 3; f <= squarenum; i += 2) loop. With the code following the loop I could easily enough determine if the number was prime or not, but getting out of the loop to print whether the number was prime or not was posing a problem. For instance,
once I determined primality, I was still stuck in the for loop
and I was printing the message "Number is not a prime" several times. I think I'm very close to solving this portion of the program, but I would still very much appreciate the source code you mentioned. By the way, once this portion is solved, I need to make the program robust in terms of being able to throw out character, real numbers, etc. In other words, the program should only handle integers for input and discard all other data types.
For the source code, I'll gladly give up 25 more points. For any suggestions regarding the robustness of this program, I'll throw in another 25. Thanks!
0
 
LVL 1

Expert Comment

by:mlaiosa
ID: 1172305
i'll post the source to www.jps.net/mlaiosa/prime, and the compiled executable.

My program started as a prime tester, but right now it goes further and lists the prime factors

as for getting out of the loop, try useing a flag like this:

for (i=3, int prime=0; f <= squarenum && !prime; i+=2)
 {
   if (n%i==0)
   {
    cout << "not prime";
    prime=1;
   }
 }

the other thing you could do (although it's bad codeing style) is use a goto


The best way to get *very* robust integer inputing is to wite your own input function.  In order to do this, you would need unbuffered keyboard input, and ANSI C does not provide this.  Must compileres, however, do support an unbuffered keyboard input function  (usu. getch() in conio.h) but becaouse this is not standard, you might not be allowed to use it.  If you would be interested in seeing some code which uses getch();  (I use Borland C 3.1/dos) just say so.

The best way of checking integer input useing standard C, would be to input a charchter string, then use atoi  to convert it to an integer.
    int atoi(const char *s);      //remember to include stdlib.h
it will return 0 if the sting is not a valid integer.  Mabe use somethign like:

#include <values.h>  //maxint is declared in here
                               //I dont think this is ANSI, but it's *very* commen

char s[50];
int n;
do
 {
  cout << "Enter a number between 2 and " << MAXINT << ": ";    
  cin >> s;
  n = atoi(s);
 } while (n < 2)


The optimization of not checking any even numbers is simple to implment and therefore increases your code's speed.  If you could think up a simple way to also skip multples of 3,5,7,11,13,etc  it could increase the speed.  Keep in mind though, it has to be very simple or it would be faster to just check if it is a factor. (i neaver thought up anthing)
0
 

Author Comment

by:BJR
ID: 1172306
Thank you very much mlaiosa. I promised 50 extra points for the added help in which I am going to make 100 points instead for your extra effort in providing such great help. Since I'm new to this and may not know the best way to add the extra 100 points, I will post a mock question with the subject 'Question for mlaiosa' in which by simply replying you will receive the 100 points. If by 7:00 P.M. tomorrow, I do not figure out a better way to get the points to you, I will go ahead and post the mock question. If by chance you know an easier way to transfer the points to you please let me know.
Thanks again.
0
 
LVL 1

Expert Comment

by:mlaiosa
ID: 1172307
The mock question is the only method I know of.  (i havent been donig this too long though)
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

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

764 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