?!?! Ideas Anyone !?!?

Was wondering if someone could give me any ideas, tips or starters on this problem:

Prime Time! – Write a program that computes and prints the nth prime number (where the user enters in which prime they would like to find). Here are a few hints to get you started:

a. You will need some variables to keep track of which prime number you’re on and keep track of where you are in your loop.

b. Remember you’ve already made a function that tests if a number is prime!

c. Think about how many numbers you actually need to check.
Last edited on
closed account (1vf9z8AR)
you can use sieve of erasthosthenes
Thanks, will take a look.
Last edited on
Don't bother using sieve of erasthosthenes. You seem to already have a function that checks if a number is a prime. They want you to write the basic idea, algorithms you can learn later.

Okay so to write this program try to think how you would determine the solution to the problem by hand, forget about computers for a second.

-> First, you look at numbers.
-> Second, you go through the numbers and check whether each number is a prime or not.
-> Third, if they're prime, you mark the prime with a pen and write whether it's the first, second, third prime number and etc. until you've got your nth prime number.

Now try to implement this with C++.

1) For looking at numbers you can use a while loop with an incremented variable/for-loop.
2) You already have a function to check whether a number is a prime
3) Once you know a number is prime, you print the number and increment a variable stating how many primes you have found so far.

Once you have found n primes you can stop the loop by breaking out of it.

Alright, I'll show the finished project tomorrow. Thanks! Sorry for all the questions today, it's high school finals.
A simple brute force solution is good enough up to, say, the millionth prime (15,485,863). But if you want to go much beyond that (the billionth prime is 22,801,763,489), then you probably want to use a segmented sieve, which will be thousands of times faster.
Last edited on
Dutch you don't have that option when you're already given a function and asked to use it though..
on the hints:
c: you only need to check to the square root of a number. many people get this mixed and try n/2 which is a LOT more numbers to check. say you want to look at 100. the factors of 100 in pairs are 1,100 (useless), 2,50 (ok so its not prime) but see there? you found 50 WHEN you found 2, because they come in pairs. ... eventually you get to 10,10 (square root of 100). if you keep going you will find 20 and 5 but you already found this as 5,20, its a repeat. once you hit the square root, it can't have a bigger factor that you have not already found.

b: you can also use what you already found. for 113, you don't have to divide by 2,3,4,5,6,7,8,9,10,... you only need to divide by the primes up to the square root .. try 2,3,5,7,11, (stop at square root as above)...

if you iterate the list of what you found already up to the root, it will be very fast. There are faster ways, but this is the way to do the 'brute force' version very quickly and its solid all the way for anything you can store in a 32 bit int and not too bad for 64 bit. you can also skip some easy values like every even number after 2, every number that ends in 5 as well. Can you think of a way to exactly skip past values that can't be prime?
Last edited on
Since you're apparently supposed to use an existing function to determine if a number is prime, I think that most of jonnin's comments don't apply. Those comments explain tricks to determine whether a number is prime.

I think the hints are pointing out:
a. you need to keep two counters for this problem, not one. The first counter stores the "candidate" number - the one that you're checking for primality. The second counter stores "number of primes found" - the count of prime numbers that you've found. The program stops when the second counter (number of primes found) reaches N.

b. The real purpose of this assignment is to show how programs are built upon other programs. You have a function to determine if a number is prime. How you'll use that function to create a different program.

c. How many numbers do you need to check to get to the 3,544th prime? The answer is "you don't know!" Well, technically I believe there are some hard limits but that's getting into some advanced math about the distribution of primes.

Two more hint that I think will help: first, add some temporary code that prints a "." each time your program finds a prime number. This will provide a simple window into the code that will help you see if you're in an infinite loop. Second, when testing, don't go crazy on the values of N. If you ask your program for the 1,000,000,000th prime, you'll probably find that it runs forever unless you make serious algorithm changes. I'd limit N to perhaps 10,000 for testing.
@jonnin, I can't imagine how that would be "not too bad for 64 bit". You should program it and try it yourself. How long does it take to find the fifty-trillionth prime? Even for 32 bits, how long does it take to find the two-hundred millionth prime?
> you don't have that option when you're already given a function and asked to use it though..
a hint is not a requirement

> Since you're apparently supposed to use an existing function to determine if
> a number is prime, I think that most of jonnin's comments don't apply.
> The real purpose of this assignment is to show how programs are built upon
> other programs
code changes
/shrug it took 5 min to get the 11 millionth, about all the patience I have @ work. You are correct; though. I was thinking the single iteration (is x prime) not the nested iteration (find the nth prime) when I said that. Brute force for the biggest prime up to 200M is a much smaller problem than the 200 millionth prime. I had the inner program on my mind when I said it. And even that is going to take hours, maybe even days, for the really big 64 bit answers. Its all relative. Its approximately 100 times faster than the non-improved brute force. for whatever that is worth.

if you want to mess with primes of magnitude > 1B you need better algorithms.
As far as the 1 million comment, though, I used to have the entire first million in a constant array, and that was before we had 1GB memory machines. I don't know how many you can cram into a static lookup before you need to start computing them, but its a fair amount --easily the first 50 to 100 million would fit on even a laptop type machine and only burn out a fraction of its memory.
Last edited on
/shrug You said "anything you can store in a 32 bit int" which goes up to the 203280221st prime = 4294967291, and you said "not bad for 64 bit". Total BS.
/shrug You simply don't know what you're talking about.
/shrug Some people just can't admit when they're wrong.
You are correct (which I already said). I was wrong.
Now i feel bad. I must've misread you. Sorry.
By the way, if the idea of sieve of eratosthenes is to find multiples and mark them as non-primes then wouldn't this take a lot of memory as opposed to the other idea which requires only computation? Or what is the implementation of the sieve of erastothenes to find nth prime in words?

Even after that, the user should define a limit to how many multiples to mark or the program will infinitely loop. So then you have to worry about calculating approximations which I think is unnecessarily complex for this simple assignment, with all due respect OP has probably just finished learning how to use a function.
if the idea of sieve of eratosthenes is to find multiples and mark them as non-primes then wouldn't this take a lot of memory as opposed to the other idea which requires only computation?

The values are bitmapped, so a byte holds 8 values.

Even in simple implementations you obviously leave out even numbers, so that takes half the memory. In more sophisticated implementations you can also leave out multiples of 3, 5, and 7.

Furthermore, in a "segmented" sieve you only need part of the bitmap in memory at a time. The idea is to have the segment fit in the cpu cache, which is the main trick to ultra-fast implementations.

The best open-source implementation is https://primesieve.org/
Thanks for the link dutch
@Grime,

Here is a simple implementation of the sieve. Even in this unoptimzed form it counts primes up to a hundred million in about half a second. It take a few seconds to count primes up to a billion, though. This is mainly due to the cpu cache being used inefficiently, the inner loop going through the entire bit array every time. If it was segmented such that the segments fit into the cache it would be a lot faster.

The bit array just represents odd values (thus halving the memory use). So

Bit:   0 1 2 3 4 ...
Value: 1 3 5 7 9 ...

Counts of primes up to x. (source: https://primes.utm.edu/howmany.html)
            x       count
           10           4	 
          100          25	 
        1,000         168	 
       10,000       1,229	 
      100,000       9,592	 
    1,000,000      78,498	 
   10,000,000     664,579	 
  100,000,000   5,761,455	 
1,000,000,000  50,847,534


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <bitset>
#include <cmath>

// bit position x represents value x*2+1
inline constexpr unsigned BitToValue(unsigned bit)
{
    return bit * 2 + 1; // return value is always odd
}

inline constexpr unsigned ValueToBit(unsigned value) // value must be odd
{
    return value / 2;
}

// test up to, but not including, this value (should be odd)
constexpr unsigned MaxNum = 100000001;

constexpr unsigned BSSize = ValueToBit(MaxNum); // number of bits in bit array

int main() {
    // static so it's not on the stack
    static std::bitset<BSSize> num; // starts zeroed (which we interpret as "prime")

    num.set(0); // bit 0 represents value 1 and 1 is not prime

    unsigned limit = ValueToBit(std::sqrt(MaxNum));

    // current prime being sieved
    unsigned pbit = 1; // bit 1 value is 3

    while (pbit <= limit)
    {
        // cross out multiples
        unsigned value = pbit * 2 + 1;
        unsigned bit = pbit + value;
        for ( ; bit < BSSize; bit += value) num.set(bit);

        // find next prime to sieve
        for (++pbit; num.test(pbit); ++pbit) ;
    }

    unsigned cnt = 1; // start count at 1 to count value 2
    //std::cout << 2 << ' ';
    for (unsigned i = 0; i < BSSize; ++i)
        if (!num.test(i)) {
            ++cnt;
            //std::cout << BitToValue(i) << ' ';
        }
    std::cout << "\ncnt: " << cnt << '\n';
}

Topic archived. No new replies allowed.