Ask Your Question
1

given a prime, finding where it is the list of primes

asked 2018-02-10 19:30:56 +0200

JRHales gravatar image

I'm writing a program that gives as an output the prime factorization of a number, and then I'm putting the primes into a matrix based on what prime number it is, (i.e 541 is the 100th prime, so if 541^2 divides my integer, then there would be a 2 in the 100th spot of my vector that represents my number)

Is there a function that takes as its input a prime and gives as an output where it is in the list of primes. (i.e we want f(541) = 100)

Thanks in advance!

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2018-02-11 21:31:36 +0200

Emmanuel Charpentier gravatar image

updated 2018-02-11 21:42:33 +0200

prime_pi?
Type:           PrimePi
String form:    prime_pi
File:           /usr/local/sage-8/local/lib/python2.7/site-packages/sage/functions/prime_pi.pyx
Docstring:     
   The prime counting function, which counts the number of primes less
   than or equal to a given value.

   INPUT:

   * "x" - a real number

   * "prime_bound" - (default 0) a real number < 2^32, "prime_pi"
     will make sure to use all the primes up to "prime_bound"
     (although, possibly more) in computing "prime_pi", this can
     potentially speedup the time of computation, at a cost to memory
     usage.

   OUTPUT:

   integer -- the number of primes <= "x"

So, given your number x,an obvious "brute-force" one-liner is :

def foo(x): return map(lambda(t):prime_pi(t[0],sqrt(x)), factor(x))
bar=Integer(round(10^10*random()))
bar
7218184858
foo(bar)
[1, 1211, 31354]

HTH,

edit flag offensive delete link more

Comments

This work! Thanks a ton!

JRHales gravatar imageJRHales ( 2018-03-10 02:58:43 +0200 )edit
0

answered 2018-02-11 21:26:14 +0200

dan_fulea gravatar image

This is a solution that puts first all "possibly relevant small primes" for the task in a list, than asks for the index of a prime in the list, in a dialog with the sage interpreter:

sage: pList = prime_range(10**6)
sage: pList.index(541)
99

(So it is the pythonically $99$.th place.)

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-02-10 19:30:56 +0200

Seen: 1,197 times

Last updated: Feb 11 '18