Re: prime number

From: SM Ryan (wyrmwif_at_tango-sierra-oscar-foxtrot-tango-dot-charlie-oscar-mike.fake.org)
Date: 05/21/04 

Date: Fri, 21 May 2004 05:34:19 -0000

e265koba@st.yatsushiro-nct.ac.jp (Chika) wrote:
# I want to create the program which asks for whether a certain number
# is a prime number using bc (calculation language).
# However, I do not understand the method of a judgment of
# a prime number.
# Please let me know someone.

In general, divide N by each prime less than it, and see if the remainder
is zero. If so for any lesser prime, it is a composite.

(1) You probably don't have a list of all prime numbers handy. Instead you
can divide by N by all numbers from 2 and N-1. That will include all primes
less than N.

(2) You can get a linear speed up by special case division by 2 and then
only dividing by subsequent odd numbers. Et cetera.

(3) If p*p>N, if pq = N, q<p. Thus you only have to test divide up sqrt(N),
not all the way to N-1.

Factorring/testing for prime has no known fast solution. Some codes depend
on this situation. 

--
SM Ryan http://www.rawbw.com/~wyrmwif/
But I do believe in this.

Relevant Pages

  • Re: Biased and unbiased std dev
    ... >invalid when n=1 and hence they divide by. ... The estimate of s^2, when divided by n-1, is unbiased because ... if the residuals of the x's from their regression ...
    (sci.stat.math)
  • Re: circular permutation
    ... one has to divide by and calculate ... >>Dirk Vdm ... Do I get part credit since my answer sometimes works? ... Dividing by (n-1) fails with 6,3 already. ...
    (sci.math)
  • Re: Finite fields
    ... "The order of an element must divide?" ... > Does an algorithm exist for finding the primitive elements of a finite ... > I am able to reduce the search space by taking a rep. of each each eq. ... > checking whether its order is one of the prime factors of (n-1). ...
    (sci.math)
  • Re: Standard Deviation
    ... If you divide that value by N or N-1 you get the variance, which is s squared if you divide by N, or sigma squared if you divide by N-1. ... From that value again, you get the standard deviation by extracting the square root, which is either s or sigma. ...
    (borland.public.delphi.non-technical)