473,842 Members | 1,876 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Prime number algorithm in C

HI,

is this is this solution to test if a number is a prime number or not:

/*
* Is n a prime number?
* Return TRUE (1): n is a prime number
* Return FALSE (0): n is a *not* a prime number
*/
int is_prime_number (int n)
{
long c;

if (n < 2) return FALSE;

for (c = 2; c < n; c++)
{
if ((n % c) == 0) return FALSE;
}
return TRUE;
}

Tia,

Chris
Nov 13 '05
32 76467
Christopher Benson-Manica <at***@nospam.c yberspace.org> wrote:
osmium <r1********@com cast.net> spoke thus:
You could improve it a lot by avoiding the test for even numbers except 2 by
changing the increment. Also, once you have reached the square root of n,
any further testing is doomed to failure so you might as well stop there.
But if you insert the square root test in the obvious way you are depending
on the compiler to be smart enough to optimize it away. So it *could*
actually get slower. :-(


He could stop at n/2 and still cut the run time in half...


He could download this:

http://www.azillionmonkeys.com/qed/32bprim.c

And be happy. :)

--
Paul Hsieh
http://www.pobox.com/~qed/
Nov 13 '05 #31
James Hu wrote:

On 2003-11-27, Dave Thompson <da************ *@worldnet.att. net> wrote:
On Sat, 22 Nov 2003 00:11:22 -0600, James Hu <jx*@despammed. com>
wrote:
On 2003-11-22, Dave Thompson <da************ *@worldnet.att. net> wrote:
> On Mon, 17 Nov 2003 11:46:08 -0600, James Hu <jx*@despammed. com>
> wrote:
>> ... v <= n/v ...
>>
> ... v * v <= n ...

But this is prone to overflow.

In general yes, though not if you are running the loop upwards (as was
the previous-post case) and n is not almost UINT_MAX (which caveat
I didn't state). But you can add a check for v <= sqrt_of_uint_ma x,
which is actually a compile-time constant although it seems difficult
to portably write it so, and I bet it's still faster than divide.


I don't doubt multiplication is faster than division on most platforms.
But, I tend to first write code that I know will work first. I've been
bitten by multiplication overflow too many times, I'm afraid.


If you're using the `%' operator to check a candidate
for divisibility, there's an excellent chance that the
`/' to check for end-of-range is "free."

for (div = 3; number / div >= div; div += 2)
if (number % div == 0)
...

Many compilers will perform just one division to generate
both the quotient and the remainder.

--
Er*********@sun .com
Nov 13 '05 #32
Eric Sosman <Er*********@su n.com> writes:
If you're using the `%' operator to check a candidate
for divisibility, there's an excellent chance that the
`/' to check for end-of-range is "free."

for (div = 3; number / div >= div; div += 2)
if (number % div == 0)
...

Many compilers will perform just one division to generate
both the quotient and the remainder.


In case it isn't smart enough, you can encourage it by using the
standard C library div() function.
--
Peter Seebach on C99:
"[F]or the most part, features were added, not removed. This sounds
great until you try to carry a full-sized printout of the standard
around for a day."
Nov 13 '05 #33

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
8417
by: Dag | last post by:
Is there a python module that includes functions for working with prime numbers? I mainly need A function that returns the Nth prime number and that returns how many prime numbers are less than N, but a prime number tester would also be nice. I'm dealing with numbers in the 10^6-10^8 range so it would have to fairly efficient Dag
9
2718
by: Greg Brunet | last post by:
In doing some testing of different but simple algorithms for getting a list of prime numbers, I ended up getting some results that seem a bit contradictory. Given the following test program (testPrimes.py) with two algorithms that both check for primes by testing only odd numbers using factors up to the square root of the value, where Primes1 is based on all of the existing primes so far, and Primes2 is based on all odd numbers, I would...
5
2729
by: Rahul | last post by:
HI. Python , with its support of arbit precision integers, can be great for number theory. So i tried writing a program for testing whether a number is prime or not. But then found my function painfully slow.Here is the function : from math import sqrt def isPrime(x): if x%2==0 or x%3==0: return 0
11
5950
by: lostinpython | last post by:
I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n > 2 is prim if no number between 2 and sqrt of n (inclusivly) evenly divides n.
11
7167
by: don | last post by:
Ok, this is a homework assignment, but can you help me out anyway...... I need a routine for figuring out if a number inputted by the user is a prime number or not...... all I'm asking for is Not the exact code ( well maybe a little) but the logic or algorithm to tell whether or not a number is prime....
3
2759
by: ckroom | last post by:
Anyone knows a good algorithm to get the next prime of a number n? prime = nextprime( n ); It's for some stuff about double rehashing, thanks. -- ckroom http://nazaries.net/~ckroom
20
6833
by: Tuvas | last post by:
I have made and recently posted a libary I made to do Modular Arithmetic and Prime numbers on my website at http://www.geocities.com/brp13/Python/index.html . I am currently in a crypotology class, and am working on building a RSA public key cryptology system for a class project. I am building the librarys just to get the experience to do so. However, I would ask if any of you know of any gaping security holes that can easily be seen from...
60
1950
by: rhle.freak | last post by:
Here is my code to generate prime numbers.It works absolutely fine when the range is *not very large*. However on initializing i with a large integer it produces erroneous results (some numbers ending in 5 ..which obviously cannot be prime numbers) can anyone please help me out with the reason?? /*Generate Prime Numbers*/ #include<stdio.h>
2
2613
by: QHorizon | last post by:
Hello, I'm new to Python (I've learned everything up to iterators so far) and fairly new to Programming. This would be my first real program: #Coordinate Geometry (The whole program is not shown) import math import sys print "Welcome to the Coordinate Geometry Calculator!"
0
9870
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10610
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10670
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10308
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7854
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5695
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4499
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4087
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3141
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.