Thread: Defining a Prime Number

Hi all,

i have a 2 dimentional(10x15) array includes random numbers from a distance between some 2 number. (numbers are spesific)

i need to find prime numbers (if there are any) from my array.

The prime number "n" is defined as :

(An integer n>=2 is said to be prime if and only if no integer k, 2<= k <= sqrt(n), divides n).

1. is this definition right? i mean i couldnt see the point here.

2. even if its right, how do i say:

"if k numbers, between 2 and sqrt(n), divides n, write "n number" down somewhere, if not, forget it".

i mean, how do i order "if divides do that, if not screw it"

i hope i could explain myself. Please help...

Yes, that's the definition!

Most programmers use a for loop to work through the numbers, but any loop might do. (I love those puns!)

Check out the modulus operator: % it gives you the remainder, after division:

N =10 % 5;

put that into a little program, and smoke it - see if you can guess the value of N.

Code:

for k equals  array[i] to array[j] maybe??, increment i and j?? 
   isPrime = test(k);
   if( isPrime equals 1 )
     printf("%d is prime", k);

IsPrime() does all the work to test for primality, for any one number you send it, as a parameter. It starts perhaps with 3, and increments by 2 (not one), since even numbers above 2 can't possibly be prime. Before the testing loop, calculate the sqrt() of k, just once, and assign it to a variable. You don't want to calculate the sqrt() of k, every time through the loop.

return 0 for any failure (no need to keep on testing). Return 1 for a prime,

A[i][j] is my array. it is 10x15 size.
that means it includes 150 numbers =D
i need to check every number if its prime or not, and collect prime ones in another array.

now:

Code:

   for(i=1;i<=10;i++)
   {
            for(j=1;j<=15;j++)
            {
               for(t=2;t<=sqrt(A[i][j]);t++) ---> this has given to me. i guess i need to use it
               {
                     if( isPrime equals 1)
                     {
                         printf("%d";&B[i]
                         } - close if
                         } - close for
                         } - close for
                         } - close for

i think this is what you're suggesting. thank you very much.
i didnt even know there is a IsPrime() function.
And i still dont know if i'm allowed to use that.

is there any way to ask if a number divides another without leaving a rest?
because i think i need to use "t" and that equation.

i think this is what you're suggesting. thank you very much.

Not quite. Your for(i) and for(j) loops are fine, but your for(t) loop should be replaced by a call to IsPrime with the current element of A, and if it's prime, store that number in B.

i didnt even know there is a IsPrime() function.
And i still dont know if i'm allowed to use that.

There is no built in IsPrime function. Adak was using a bit of pseudo code. You will have to write the IsPrime function yourself. You're teacher gave you a big clue as to how it works though. This is half of it:

Code:

for (t = 2; t <= sqrt(A[i][j]); t++) {
    // fill in your remainder check here to determine if it's prime
}

is there any way to ask if a number divides another without leaving a rest?
because i think i need to use "t" and that equation.

Adak already answered that question in post #2, maybe you missed it:

Originally Posted by Adak

Check out the modulus operator: % it gives you the remainder, after division:

N =10 % 5;

put that into a little program, and smoke it - see if you can guess the value of N.

it exactly is.. =D
i get it now.

i did it with mod test, and sth came out like this..
its not working though...

Code:

#include <stdio.h>
#include <stdlib.h>
#define SATIR 10
#define SUTUN 15
#define SATIRR 100  

int main()
{
  int i;
  int j;
  int A [SATIR][SUTUN];
  int B [SATIRR];
  int k;
  
       for (i = 0; i < SATIR; i++ ) {
  
        for (j = 0; j < SUTUN; j++ ) {
            
            A [i][j] = 100+(rand()%400);
            
            printf ( "%5d", A [i][j]);
            }
            printf ( "\n" );
            }      




for(i=1;i<=10;i++)
   {
            for(j=1;j<=15;j++)
            {
                        for(k=2;k<=sqrt(A[i][j]);k++) 
                        {if((A[i][j])%k == 0 )                              
                              {
                                   printf("");                             
                                                }
                                   else
                                   {
                                   B[i]=A[i][j];
                                   }
                                         
                                         }
                                         }
                                         }
                                         printf("\n");
                                         printf("%7d", B[i]);
                                         printf("\n");
                                         
                                         system("PAUSE");
                                         return 0;
                                         
                                         
                                         }

Adak basically gave you the program structure. You only have a few lines to fill in. I might make a few suggestions though.

Code:

                       B[++m] = k;

Should probably be B[m++]. Since it's initialized to zero, we want to store the 0-th element, then increment, otherwise we will have garbage in B[0] and start at B[1].

Code:

for(i=1;i<=10;i++)
   {
            for(j=1;j<=15;j++)
            {

Arrays always start indexing at zero. This should be i = 0; i < SATIR, and similar for j. You bothered to make those pretty #define statements, so use 'em.

hello again.

i very appreciate the help last night.
my brain fried, and i took a break.

worked a little on again today. and solved many things.
program successfully runs, but i guess there is a problem with isPrime function here.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SATIR 10
#define SUTUN 15
#define SATIRR 150  

int isPrime(int k);
int main(void)
{
  int i;
  int j;
  int A [SATIR][SUTUN];
  int B [SATIRR];
  int k;
  int m;
  
       for (i = 0; i < SATIR; i++ ) {
  
        for (j = 0; j < SUTUN; j++ ) {
            
            A [i][j] = 100+(rand()%400);
            
            printf ( "%5d", A [i][j]);
            }
            printf ( "\n" );
            }      



for(i=0,m=0;i<10;i++)
   {
            for(j=0;j<15;j++)
            {
                             k=A[i][j];
                             if(isPrime(k))
                 {
                       B[m] = k; 
                       }
                       else
                       {
                           B[m]= 0;
                           }
                       m++;
                       }
                       }
                       printf("\n");
                       for(m=0;m<150;m++)
                       {
                       printf("%5d", B[m]);
                       }
                       printf("\n");
                       system("PAUSE");
                       return 0;
                       }
                       
                       
                       
                       
   int isPrime(int k)
   {
       
       int sqr;
       sqr=sqrt(k);
       int p=2;
       while(p<=sqrt(k))  {
                            if(k % p == 0)
                            {
                            return 0;
                            break;
                            }
                            else
                            {
                            return 1;
                            }
                            
                            p++;
                            }
                            }

in isPrime,
it only takes p value as starter value (in this case 2 )
is break doesen't work? or there is something else.

is break doesen't work? or there is something else.

break is irrelevant following a return statement. The function returns immediately, so you can't break out of the loop.

i guess there is a problem with isPrime function here.

Your problem is the location of return 1. The algorithm is this:

Code:

for every number p from 2 to sqrt(k)
    if p divides evenly into k
        return not prime

return prime

Your code is returning "this number is prime" inside the loop, which means that the first number between 2 and sqrt(k) that doesn't divide evenly into k will make your function return 1, signifying prime. Take 25 as an example (definitely not prime, 5 * 5 = 25). The first iteration of your loop, p is 2, which is less than sqrt(k) or 5, so we enter the loop, you check if 2 goes evenly into 25, which it doesn't, so you enter the else clause and return 1. Your main function now incorrectly records 25 as prime.

A few minor notes:
1. You pre-compute sqrt(k) and store it in sqr. This is a good idea, but you don't use it in your loop, so you recalculate sqrt(k) for every iteration, which is wasteful.
2. Use a for loop for the isPrime function, it's a bit cleaner:

Code:

for (p = 2; p < sqr; p++)

3. Ditch the superfluous 'break' in your isPrime function.