Primes

From NARS2000
Jump to navigationJump to search
Z←πR returns an integer vector consisting of the prime factors of R.
R is a scalar or one-element vector consisting of a positive integer to be factored.
Z is an integer vector whose values are the prime factors of R.


For example,

      π120
2 2 2 3 5

      ×/⎕←π⎕←¯1+2*62
4611686018427387903
3 715827883 2147483647
4611686018427387903

      π¯1+2*61
2305843009213693951

      ⍴π1
0
      c←×/(a b)←1π?2⍴10*25x  ⍝ Create two random 25-digit primes and their product
      a b c
213379889007584782100623 7822072437371562999056237 1669072948495632279507879309030439547039369735651 
      πc  ⍝ Factor the 50-digit number
213379889007584782100623 7822072437371562999056237 
      ⎕T-(πc)⊢⊢⎕T  ⍝ How many seconds of CPU time to factor a 50-digit number?
0.6204937084112316



Z←LπR returns an array whose values depend upon which number-theoretic function chosen by L is applied to R.
L is an integer scalar whose meaning is as follows
¯2   Rth prime function
¯1   Previous prime function
 0   Primality test function
 1   Next prime function
 2   Number of primes function
10   Divisor count function
11   Divisor sum function
12   Möbius function function
13   Euler totient function
R is an array consisting of positive integers to which one of the above functions is applied, element by element.
Z is an integer array of the same shape as R.


Rth Prime Function

The Rth prime function (¯2πR) returns the Rth prime where 2 is the first prime. This function is sensitive to the index origin.

For example, how many primes are less then or equal to 1000003?

      ¯2π1000003
15485927

Previous Prime Function

The previous prime function (¯1πR) returns the prime that immediately precedes R.

For example, what is the prime that immediately precedes 1000000?

      ¯1π1000000
999983

Primality Test

The primality test function (0πR) returns a 1 if R is a prime and 0 if not.

For example, is 1000003 a prime?

      0π1000003
1

List the primes up to 100

      ⍸0π⍳100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Next Prime Function

The next prime function (1πR) returns the prime that immediately follows R.

For example, what is the next prime after 1000000?

      1π1000000
1000003

Number Of Primes Function

The number of primes function (2πR) returns number of primes less than or equal to R.

For example, what is the 15485927th prime?

      2π15485927
1000003

Divisor Count Function

The divisor count function (10πR) returns the number of divisors of a number. It is the same as ×/1+∪⍦πR where πR returns the prime factors of R and ∪⍦ counts the number of occurrences of unique elements (in this case, the exponent vector of the unique primes). A divisor then consists of the product of zero or more of the unique primes which is why ×/1+ counts them.

Divisor Sum Function

The divisor sum function (11πR) returns the sum of the divisors of a number. It is the same as ×/(¯1+(∪f)*1+∪⍦f)÷¯1+∪f←πR1. This function is used to recognize deficient, perfect, and abundant numbers.

Möbius Function

The Möbius function (12πR) returns information about the square free properties of R. If R is square free, the function returns 1 if R has an even number of prime factors, and ¯1 if it has an odd number of prime factors. If the argument is not square free, the function returns 0. It is used in the Möbius Inversion Formula to invert general arithmetic functions.

Totient Function

The totient function (13πR) (also called Euler's Totient Function) returns the number of positive integers less than or equal to R that are relatively prime to it (i.e., having no common positive factors other than 1).

Examples

Add together the first 100 primes:

The Rth prime function (¯2πR) gives the value of the Rth prime, as in

      ¯2π100
541

The Index function (⍳R) produces a vector of integers of length R, as in

      ⍳¯2π100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 541

The Primality Test function (0πR) returns a 1 if the corresponding element in R is a prime, 0 otherwise, as in

      0π⍳¯2π100
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 ... 1

The Indices function (⍸R) converts the argument R to indices (equivalent to (,R)/⍳×/⍴R), as in

      ⍸0π⍳¯2π100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 ... 541

Finally, those numbers may be added together using plus reduction (+/), as in

      +/⍸0π⍳¯2π100
24133

Notes

1 Formula for sum of divisors