Board index » delphi » Pascal code for finding prime numbers from 1 to 1000

Will

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Pascal code for finding prime numbers from 1 to 1000

I was wondering if anyone has code that can tell a user if there number they
input (1 to 1000) is a prime number? Anything would be appreciated as I'm
very new to Pascal and I'm using Turbo Pascal 5.5.
 
Mike Copela

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


Quote
> I was wondering if anyone has code that can tell a user if there number they
> input (1 to 1000) is a prime number? Anything would be appreciated as I'm
> very new to Pascal and I'm using Turbo Pascal 5.5.

   Is it really in your best interest(s) to have this (homework
assignment) given to you?  You'll benefit most from (1) researching what
prime numbers are and (2) doing this exercise yourself.
   For one way, look up the Sieve of Erastosthenes (sp).
ViLNiu

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


I have made a program made in TP7 which does this. Would you like to have
the source?

ViLNiuS

Will <W...@hotmail.com> schreef in berichtnieuws
3EbL4.1137$9B.147...@news.bc.tac.net...

Quote
> I was wondering if anyone has code that can tell a user if there number
they
> input (1 to 1000) is a prime number? Anything would be appreciated as I'm
> very new to Pascal and I'm using Turbo Pascal 5.5.

Dr John Stockto

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


JRS:  In article <3EbL4.1137$9B.147...@news.bc.tac.net> of Tue, 18 Apr
2000 22:40:16 seen in news:comp.lang.pascal.borland, Will

Quote
<W...@hotmail.com> wrote:
>I was wondering if anyone has code that can tell a user if there number they
>input (1 to 1000) is a prime number? Anything would be appreciated as I'm
>very new to Pascal and I'm using Turbo Pascal 5.5.

A Web search may help, especially if you can spell Eratosthenes.

For that limited range, however, it's best to note that any non-prime
will be divisible by a number in 2..31; or that any non-prime will be
divisible by an odd number in 3..31.  UNTESTED :

Prime := true ; J := 3 ;
repeat
  if (X mod J) = 0 then begin Prime := false ; BREAK end ;
  Inc(J, 2) until (J>=X) or (J>31) ;

The fact that BREAK cannot be used in TP5.5 (IIRC) is left for you to
resolve; there is at least one good way and one not so good way.

You could make use of Sqrt too; and if you think how to you should also
see how to get the same effect without using it.

--
? John Stockton, Surrey, UK.  j...@merlyn.demon.co.uk   Turnpike v4.00   MIME. ?
 <URL: http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
 <URL: ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ;
 <URL: http://www.merlyn.demon.co.uk/clpb-faq.txt> Pedt Scragg: c.l.p.b. mFAQ.

Clif Pen

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


Quote
On Tue, 18 Apr 2000 22:40:16 -0700, "Will" <W...@hotmail.com> wrote:
>I was wondering if anyone has code that can tell a user if there number they
>input (1 to 1000) is a prime number? Anything would be appreciated as I'm
>very new to Pascal and I'm using Turbo Pascal 5.5.

Do a search on the Internet for "Eratosthenes", "Chinese Remainder",
"Euclid's Algorithm" and "Euclids's GCD" and you will find what you
need to test prime numbers.

For your relatively small number of 1,000 as a maximum, the Sieve of
Eratosthenes implemented with an array appears the easiest. In this
method you would start at the first prime after 1, i.e. 2, and cross
out all following numbers through 1000 that are multiples of 2. Now
you start with the next number that has not been crossed out, 3, and
cross out all multiples of 3 and so on. The numbers not crossed out
are the primes less than 1,000.

For lists of primes longer than this, Euclid's greatest common divisor
(GCD) can be used. Basically, if y MOD x = 0 then y is not a prime
number because x is a divisor. If the GCD of x and y is 1 then then x
and y are relatively prime. You can start with the lowest primes
searching for a GCD = 1 to find the next prime, add that to your list
and use that new prime to search for common divisors also. A little
thought will show that you need not use test numbers higher than the
square root of a potential prime.

Clif <clifp...@airmail.net>

m..

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


Quote
Will <W...@hotmail.com> wrote:
> I was wondering if anyone has code that can tell a user if there number they
> input (1 to 1000) is a prime number? Anything would be appreciated as I'm
> very new to Pascal and I'm using Turbo Pascal 5.5.

There is at least 1 in the SWAG. (written by me!)   It's about
10 or so lines of code, so it's not as difficult as it looks.
Timo Sal

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


In article <3EbL4.1137$9B.147...@news.bc.tac.net>,
Quote
Will <W...@hotmail.com> wrote:

:I was wondering if anyone has code that can tell a user if there number they
:input (1 to 1000) is a prime number? Anything would be appreciated as I'm

 153) How can I test if an integer number is a prime?

 165966 Jan 8 2000 ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip
 tsfaqp.zip Common Turbo Pascal Questions and Timo's answers, linked

   All the best, Timo

--
Prof. Timo Salmi ftp & http://garbo.uwasa.fi/ archives 193.166.120.5
Department of Accounting and Business Finance  ; University of Vaasa
mailto:t...@uwasa.fi <http://www.uwasa.fi/~ts/>  ; FIN-65101,  Finland
Timo's  FAQ  materials  at   http://www.uwasa.fi/~ts/http/tsfaq.html

Dr John Stockto

Delphi Developer
Wed, 18 Jun 1902 08:00:00 GMT

Re:Pascal code for finding prime numbers from 1 to 1000


JRS:  In article <8dr320$...@loisto.uwasa.fi> of Sat, 22 Apr 2000
05:33:36 seen in news:comp.lang.pascal.borland, Timo Salmi <t...@UWasa.Fi>
wrote:

Quote
>In article <3EbL4.1137$9B.147...@news.bc.tac.net>,
>Will <W...@hotmail.com> wrote:
>:I was wondering if anyone has code that can tell a user if there number they
>:input (1 to 1000) is a prime number? Anything would be appreciated as I'm

> 153) How can I test if an integer number is a prime?

> 165966 Jan 8 2000 ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip
> tsfaqp.zip Common Turbo Pascal Questions and Timo's answers, linked

In that, I believe that Trunc could be used where Round now is; and it
gives the wrong result for n<2.

One might be able to avoid a float operation (Sqrt) by using (n+1)^2 =
(n^2 + 2*n + 1) -- SLIGHTLY TESTED :

  fn := true ; j := 2 ; k := 4 ;
  repeat
    if (n mod j) = 0 then begin fn := false ; BREAK end ;
    Inc(k, j) ; Inc(j) ; Inc(k, j) until k>n ;

Though that also fails for n=2; perhaps the loop should be changed to a
while loop.

--
? John Stockton, Surrey, UK.  j...@merlyn.demon.co.uk   Turnpike v4.00   MIME. ?
 <URL: http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
 <URL: ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ;
 <URL: http://www.merlyn.demon.co.uk/clpb-faq.txt> Pedt Scragg: c.l.p.b. mFAQ.

Other Threads

1. 2 - 1000 digit numbers multiplier CODE

2. trying to find a prime number

3. Prime Number Finding Program

4. Help with cleaning code on sub-function used to check if number is a prime

5. prime numbers SQR in Pascal

6. Pascal-Code to find the number of floppy-Drives

7. 1000 -> 1,000.00 , home ->Home

8. Prime number program

9. Help: Function to determine Prime Numbers (TP5.5)

10. Prime Number generator