Study guides

☆☆

Q: Write an algorithm draw flowchart to find that the given no is prime or not?

Write your answer...

Submit

Still have questions?

Continue Learning about Engineering

The algorithm is fairly straightforward. For any integer i greater than or equal to zero:i is non-prime if i is less than 2.otherwise, i is prime if i is 2.otherwise, i is non-prime if i is greater than 2 but is divisible by 2.otherwise, i is non-prime if it has any prime factors less than or equal to its square root.otherwise, i is prime.Step 4 is easier to implement by testing all odd divisors from 3 to the square root of i.

#include<stdio.h> #include<conio.h> int i=1, count=0,n; clrscr(); printf("Enter Any Number"); scanf("%d", &n); while(i<n) if(n%i==0) { count++; i++; } if(count==2) printf("Given Number is Prime"); else printf("Given Number is not Prime"); getch(); }

Use Euclid's algorithm to find the greatest common factor. This algorithm is much simpler to program than the method taught in school (the method that involves finding prime factors). If the greatest common factor is 1, the numbers are relatively prime.

int number; int i=2; while (i<number) { if(number%i==0) { printf("Not a prime no."); break; } else printf("number entered is prime"); getch(); }

Any number that has one or more prime factors is a composite number. All others are prime numbers. Prime factors are themselves prime numbers, but rather than test every potential factor to determine if it is prime, it is much quicker to simply test every odd factor in the range 3 to the square root of the number. The only exception is even numbers which are all composite except 2. Thus we use the following algorithm (for all positive integers): 1) If the number is less than 2 then the number is composite. 2) If the number is even then it is prime if it is 2 otherwise it is composite. 3) If the number is odd and is evenly divisible by any odd integer in the range 3 to the square root of the number (inclusive) then the number is composite. 4) All other numbers are prime. To express this algorithm as a function in C++, we would use the following: bool is_prime (unsigned value) { // algorithm part 1) if (value<2) return false; // algorithm part 2) if (!(value%2)) return value==2; // algorithm part 3) unsigned max_factor = (unsigned) sqrt (value) + 1; for (unsigned factor=3; factor<max_factor; ++factor) { if (!(value%factor)) return false; } // algorithm part 4) return true; }

Related questions

Shrek and Donkey

You can write out this algorithm. This will then be programmed into the device to make determining prime numbers easier.

Develop an algorithm to display all prime numbers from 2 to 100. Give both the pseudocode version and the flowchart version. Convert your pseudocode into a Java program.

yes

The algorithm is fairly straightforward. For any integer i greater than or equal to zero:i is non-prime if i is less than 2.otherwise, i is prime if i is 2.otherwise, i is non-prime if i is greater than 2 but is divisible by 2.otherwise, i is non-prime if it has any prime factors less than or equal to its square root.otherwise, i is prime.Step 4 is easier to implement by testing all odd divisors from 3 to the square root of i.

The sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.

where to start? do you have an algorithm and just want to implement it in java? depends on how big N is, as that will determine which method is most efficient

Euclid's algorithm is probably the most commonly used 'formula' for that purpose. If the greatest common factor is 1, the numbers are relatively prime. See the related question for an example of Euclid's algorithm.

Write a function that implements an algorithm that checks to see if a particular integer is prime (returning a boolean). Write a program that uses that function on each number from 1 to 100, and if true, displays that number.

What exactly do you mean "yields only prime numbers"? If you mean a formula that when given the numbers n=1, 2, 3, ... and so on generates the nth prime number (or a different prime number for each n) then no. If you mean an algorithm whereby a number can be tested to be a prime number then yes. (Using this prime_test algorithm, a simple algorithm can be written that would supply numbers one at a time to it and use its result to decide whether to yield the tested number or not, only yielding those numbers which pass the test.)

If the number is < 2 then it is not a prime. If the number is == 2 then it is a prime. If the number is divisible by 2 then it is not a prime and so on.

295 is composite - 5 x 59.

People also asked