Hello and welcome back.
I wanted to give you another challenge, another assignment.
Obviously, this one's going to be all about arrays.
I want you to get familiar with how to use an array, how to access an
array and how to create an array.
So you should write a c program that's going to find all the
prime numbers from 3 to 100.
And we're going to do it very efficiently.
So we're going to use a little algorithm that makes you use an
array, but very simple program.
It's just going to display as output, all the prime numbers from 3 to 100.
And the reason you don't do 0 to 3 is because you're going to hard
code those, it's pretty simple.
First 2 our first 2 prime numbers are 1 and 2 that are non-0.
So there's going to be no input to this program, just output.
And the output is going to be each prime number separated
by a space on a single line.
It's pretty basic, all the way up to 100.
You're going to need to create an array that will store each
prime number as it is generated.
You can hard code the first 2 prime numbers, which are
2 and 3 in the primes array.
So what I’d envision here is that you would create an array, you would
name it primes and you would just hard code the first 2 in there.
And it's important to hard code them too because the algorithm
that we're going to use to find prime numbers is going to compare
for any other prime numbers, and I’ll explain that in a second.
You want to utilize the loops for this assignment to only find
the prime numbers up to 100.
So right off the bat, you should envision a loop at least to display
the prime numbers that you found.
So that would probably be the ending loop, the loop at the end of your
program that just goes through the primes array and displays
everything that's inside there.
now if you're finding all the prime numbers up to 100, you're not going
to need to make the size of the array probably more than 50 because I don't
think there's more than 50 prime numbers, all the way up to 100, but
you're not going to be able to set it exactly correctly because you don't
know how many prime numbers there are.
So I would say when you create the primes array, just make a size of 100.
So you definitely need a loop to print them out at the end.
you're going to need another loop to try to find the prime numbers.
And you can find the prime numbers any algorithm you want, but what I would
use is I would use something like this because there's more reason to use
an array if you do this algorithm.
So the criteria that can be used to identify a prime number is
that a number is considered prime if it is not evenly divisible by
any other previous prime numbers.
And there's also more to that algorithm, but
that's the starting point.
You also want to only look up to a certain number.
So you can use the following as an x condition in the innermost loop.
So again, what you're going to need to have here is you're probably
going to need to have 2 loops.
We already mentioned the third loop at the bottom printing out the
data, but you're going to need to have 2 loops for this assignment.
And the algorithm that I’m discussing here is a more improved algorithm.
So this is why you want to do it.
Now if you want to find prime numbers in a different way, that's okay as
long as you use an array because the whole purpose of assignment is not
to understand prime numbers, it's to understand how to use arrays.
By looking at the previously generated prime numbers that forces
you to use an array and you'd store that each prime number as
it gets generated as I mentioned.
And the other way that you can make it even more optimal is that you
don't want to look at even numbers.
So if you're going through each number from 3 to 100 and you're
checking if that's prime, you can ignore the even numbers because even
numbers are never going to be prime.
So in the outermost loop or the innermost loop, you can check to
see if the prime is divisible by the other primes or make sure it's not
even you can check that and skip it.
And then this other axis condition in the innermost loop is to make
sure that the value of the p does not exceed the square root of the primes,
that's other part of the algorithm.
So this might not make full sense, but basically these are some of the
criteria that I want you to follow.
Skip any checks for even numbers, and then the algorithm is to look
for any previous prime numbers that were generated and also to
check whether or not p does not exceed the square root of the of
the primes because that's another way to check for a prime number.
So you're going to need to have a for loop which basically goes
from 5 to 100 and then you can increment that by 2 so that
you only look for odd numbers.
And then in an inner for loop you have inside there, you're going to
want to go from 1 until this other value p divided by prime sub-I is
greater than equal to prime sub-I.
And you'll probably also want to make sure that the number is not prime.
So you don't want to exceed a certain check and then you also want
to jump out of the inner loop if you actually found a prime number.
And so the way that you can check for prime number if your current number
is divisible by any previous prime, so you can look at the primes array.
And if the modulus for that is equal to 0, then you
don't have a prime number.
Otherwise, if you've done this whole check in this entire loop and
you've got out of there with already exceeding the prime sub-I is greater
than prime sub-I the square root issue and you not actually found
a prime number, then that means that you can then add that prime
number to your primes array and then just print out the primes array.
So the actual algorithm doesn't seem as confusing as I’m making it.
Again, try to give you as many pseudocode hints there
as possible with the outer for loop in the inner for loop.
But you're going to need to access arrays, you're going to read
arrays, you're going to look at an array to see previous values.
It's going to get you really familiar with arrays.
So good luck, and I’ll provide a solution in the next lecture that
will make a lot more sense, but these are the requirements and some hits.
Thank you.