-4

I have this task:

Design a program which fills a matrix, of size n x n, with prime entries (its entries must be prime numbers).

Now, I have a subroutine which reads and impries any matrix, when the user gives the entries of the matrix, and also have a subroutine which impries the prime numbers less than a given number of the user (as an array). What I can't do is try to combine these subroutines. Could you give me some good advices, please?

GraphicsMuncher
  • 4,583
  • 4
  • 35
  • 50
Alexei0709
  • 113
  • 1
  • 5
  • [How to ask about homework](http://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions). Make a good faith attempt to solve the problem yourself first. Ask about *specific* problems with your *existing* implementation. Admit that the question is homework. Be aware of school policy regarding outside help. Never use code you don't understand. – rsjaffe Apr 17 '16 at 00:06
  • Make an appointment [to see your rubber duck](https://en.wikipedia.org/wiki/Rubber_duck_debugging). – Sam Varshavchik Apr 17 '16 at 00:21
  • Rory Jaffe: it's not quite a homework. One month ago, my teacher puts me this question, not as a homework, but as a good practice to understand arrays. My big issue (or what I consider my main problem) is the next: how can I make the program recongize how many primes (n^2) should be in the matrix? – Alexei0709 Apr 17 '16 at 00:22
  • Are you possibly asking about [prime counting function](https://en.wikipedia.org/wiki/Prime-counting_function)? Not the best idea for this task. Even if you have a subroutine which gives you all numbers less than a given number, it doesn't mean you should use it. Alf suggested a better approach. – ptrj Apr 17 '16 at 01:15
  • What Alf proposes me is use the sieve of Eratostenes (I have it already in a code, and actually the code gives an array of prime numbers less or equal than a given number). So, what's on my mind right now is try to "convert" an array into a matrix, or kind of; is my approach correct? – Alexei0709 Apr 17 '16 at 01:28
  • @Alexei0709 Oh, you're right. I misunderstood the problem. I'll try to write something about the prime counting function later. – ptrj Apr 18 '16 at 00:05

1 Answers1

0

(I admit I misunderstood the question, as probably did some other commentators of the original post. It's relatively simple but not that trivial as it looks. For small inputs a naive approach 4. may work best.)

Let me reformulate the task:

Given a number N, find first N prime numbers.

Since you already implemented the sieve of Eratosthenes, the question is which number should be chosen as the upper limit for the sieve. Essentially, this is equivalent to finding the inverse of the prime counting function or to finding x, possibly smallest, such that

pi(x) >= N

(where pi is the prime counting function).

  1. The article in wikipedia contains some hints, for example the inequality

    pi(x) >= x/log(x).

    So, one approach could rely on finding an approximate solution of the equation

    x/log(x) = N,

    which would be later used in the sieve of Eratosthenes. This can be done relatively easy (for small N even binary search will do).

  2. There is, however, a widening gap between x/log(x) and pi(x) (see the table in the linked wikipedia article). So if we are really concerned about memory we could try a better inequality:

    pi(x) >= li(x),      (true for x <= 10^19)

    where li is the logarithmic integral. This one gives a better approximation but a) we'd need some external library with the function 'li' and b) the inequality may not be true for very large x (probably not an issue here).

    And if we'd like to improve the estimation even further (and for all x), we may need the assumption that the Riemann Hypothesis is true (yes, it's scary).

  3. There are some direct algorithms for calculating pi but it's not worth using them for this task.

  4. More direct approach:

    • make a guess for the upper limit in the sieve, say A, and run the sieve

    • if number of primes is too small, choose a larger upper limit, say B, and run the sieve, starting with the primes already found, for numbers in interval (A,B]; repeat.

  5. If in 4. you are off by very few primes, a brute force may be faster. I've just found this post with interesting answers.

Community
  • 1
  • 1
ptrj
  • 5,152
  • 18
  • 31