Hello and welcome.
I would like to provide a demonstration a solution to
our previous challenge which was to write a program that
generates prime numbers.
And so again, the whole point of this program was to use an
array, you want to learn all about arrays and do by doing this.
So I tried to describe the prime number algorithm before.
But to just mention it again, you can check whether or not
a prime is a prime number.
The prime number it means that uh it's not evenly divisible
by any other prime number.
So that's the notion algorithm that we're going to go by.
And the reason that's why it's a prime number is because any
non-prime integer can be expressed as a multiple of prime factors.
So for example 20 has the prime factors 2 2 and 5.
So by knowing this, this tells you that prime numbers are not evenly
divisible by any other prime number.
So this can help make a very efficient prime number test.
So what you can do is you can check the previously
generated prime numbers.
So we can store our previously generated prime numbers in
an array, and that's how we can find this information.
Also any 9 prime integer n must have as one of its factors an
integer that is less than or equal to the square root of n.
So this means that it's only necessary to determine if a given integer
is prime by testing it for even divisibility against all prime factors
up to the square root of the integer.
So you can stop right there and again it makes it more efficient.
This is going to be noticeable in my inner loop when I
jump out to determine if I haven't found a prime number.
I’m going to jump out if I get to the square root of the integer,
it's an exit condition essentially.
So let's go through and the way that you can check for that is
you just say p divided by primes is greater than prime sub-I, and
we'll use that in innermost loop to test whether or not the value of p
exceeds the square root of prime's I.
So let's go ahead and bring up code blocks to start writing some code.
We're going to do the basics here, create a project.
We'll name our project called primes.
So let's go to new project,
and let's go to console application.
And we're going to name it primes.
Say next, we're not going to use this compiler.
I was playing around with compilers I want to make sure
I have the right compiler I’ll just use the cygwin compiler.
So it's generating my main source file, and it's empty.
Let's get rid of the printf and start writing some code.
We're going to include a file called standard bull.
I haven't done this yet; I’ve been creating my Booleans as underscores.
Let's just do a little test, I want to be able to do bool.
So now we can use bools.
So normally in C89, the data type for true or false is underscore bool.
But you can actually have a type definition in later versions
and in the standard bool file to just use bools and also allows
you to use true false as values.
So we got to create some variables here first.
We're going to create our counter which we're just going to name p.
That's going to be our counter for our loop from when we
check from p to 100 numbers.
That's going to be our outer loop.
We're also going to create a variable for our inner loop counter.
This is where we check our previous primes.
Actually, we won't initialize it here we'll initialize it in the loop.
We're going to create our array which is going to be an integer of
primes and it's going to be size 50.
And we're not going to initialize it to anything but 0 for now.
And then we're going to create a prime index, and this will help us
skip all of our even numbers, and we're just going to set that to 2.
This variable is actually going to make sure we start at the
correct index because we're going to hard code the first 2 numbers.
That's what we're going to do first.
We're going to hard code our first 2 prime numbers.
So this is how we can access array.
We know how to create an array in line 10, you just specify the data type
followed by the name and then in the square brackets we specify the size.
And then we're initializing everything to 0, this is a
C99 trait that we can do.
And to assign data to an array, I can just say the array name
and then the index value.
Remember, arrays are 0 based.
So I’m going to say prime sub-0.
And the first prime is going to be 2.
2 is the first prime number.
Second prime number is going to be equal to 3.
This way I have some prime numbers that I can previously
test to find additional primes.
And now comes our looping.
We're going to need outer for loop that goes through all
the numbers from 5 until 100.
We know 4 is not a prime number so I’m just starting at 5.
So we can say 4 p equals 5, p is less than or equal to 100 and then
we're going to skip even numbers.
So we're going to say p equals p plus 2.
We don't need to look in any numbers, that's going to be our outer loop.
And again, you should be testing as you're going.
Now we're also going to set up a Boolean variable which
will tell us whether or not we found a prime number.
So here's where I can use bool, and I’m going to just create a
local variable Boolean is prime.
I’m going to have that initialized to say is true because I’m only
going to set it to false if I’ve gone through the entire list of
previously generated primes or I’ve got to the latest prime and
make sure it's not the square root.
So is prime is going to be equal to true for each iteration
from 5 to 100 skipping 2.
Now my inner loop is going to go through all of our prime numbers
that we have previously generated.
Make we haven't gone greater than the square root of the I.
So we're going to go through all of the numbers until we get to the square
root, that can be our x condition.
We're also going to exit if we found a prime number.
So we're going to say if is prime is true and we've gone through
our limit, which is going to be p divided by prime sub-I is greater
than or equal to primes sub-I.
And then we're going to plus plus I is our loop control variable.
This is really the key to the algorithm.
So we're going to try to find all our primes from 5
to 100 skipping even numbers.
And then in our inner loop, we're going to start at 1, we're going to
go all the way until we either set is prime to true or we've reached
our exit condition, which is the number p divided by prime sub-I is
greater than prime sub-I, and that's essentially ending to make our when
we find a square root because that's another condition of the algorithm.
If that's our loop, inside of our loop, we're going to
actually check for primes.
The way that a number is prime is you divide it by the number.
And if you don't have a 0, then you're good to go.
So you can just do a p mod prime sub-I equals equals 0.
And if that is true,
then you don't have a prime number.
So you can set the Boolean equal to false.
And then that's what we do for the entire loop because
all we're doing is we're going to set the Boolean to false.
And that will tell us we didn't find a prime number, so we don't want to add
p to our primes array.
Okay, so the last thing to do is we just check if the Boolean was set to true,
if it was set to true, then we want to fill in our array.
We want to add it to the array. So we're adding to the arrays we find prime.
So we just say primes and then we say prime index.
Because, remember, this is the one that's really represented by the index
for where we want to put into the array, which is we want to start at element 3
which is index 2.
So we want to make sure we put it in the right spot in the array, and
we just set it to p because p was the prime number that we found because remember this is the outer for loop.
We're trying to check if that's a prime number.
We start at 5.
We say if 5 is going to be prime, if we can go to these numbers starting at 1
and then compare against any previous primes and if it's not divisible by 0,
then we're good and we have to do that for everything.
And then the last thing we want to do is we just want to
increment that prime index.
So the next time we find a prime number, we're in the right index.
And that is it.
And this is the entire algorithm to find prime numbers.
So you want to save that and build it, make sure everything's good to go.
We're good.
So I like adding the true false values by including standard
bool, don't forget about that.
And then the last thing we have to do is we just have to
print out the prime numbers.
So we can just have a simple for loop.
And we're going to print them all on the same line, so we're
not going to add a line feed.
So what we're going to do is we're going to re-instantiate
our loop control variable to 0 I.
We're going to go all the way to our prime index, which is going to be
the size of everything in the array and just print it out in a single
line, percent I or d and prime sub-I.
And then at the very end, we'll add a line feed.
Something like that with a semicolon.
But again, things to notice in this program.
First, notice the indentation, all the blocks are indented.
We sometimes use brackets when we have more than one statement inside
of our blocks, sometimes we don't.
In this if statement on line 25, we didn't use any brackets.
For loops should become somewhat second nature by now.
Really what you want to gain from this assignment is the arrays.
So we're creating an array called primes, setting it size 50, initializing everything to 0.
And then we're setting the first 2 elements to 2 and 3 and then
this whole algorithm from 19 to lines 32 is determining if it's
prime by looking at the array in the previous prime numbers.
And also jumping out when you're greater than the square root.
And so again you see a lot of square brackets here to access
arrays and to assign values to arrays and everything,
it's pretty straightforward.
So let's build this and see what happens.
We have no warnings, no errors.
If we run this, what you see is output is all the prime
numbers to 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 and so on.
Those are all prime numbers.
And prime number is something that only was only a factor of itself.
You can't divide that by any other number and have a no remainder.
So 97 the only 2 factors that go into that are 1 and 97.
So again a nice little quick program.
I’ll provide the solution.
You can analyze it.
But again key takeaways, everything about the arrays and also the
standard bool that I used, that allowed us to create Boolean data
types without the underscore capital b and also allows you to use true
false values as opposed to 1 and 0.
Hope this helps. Thank you.