ok weird question

Giblet

right im in college and i have to do this program which involves printing out all the prime numbers up too 253
anyone got any algorithms or formulae that would distinguish prime numbers from the rest

Puck

What language are you using?

Giblet

ah you see heres the problem
it's the lecturers own programming language for simpiltons like myself
i need an algorithm that resembles basic or psuedo code
his launguage has while loops and repeats, if statements and most basic operators (+,-,*,^) but not square root
so i need a psuedocode algorithm or a simple BASIC one
any help would be appreciated

Enygma

Doesn't really matter about the language.
The way I learned to do this is called the Sieve of Eratosthenes (sp?)
Basically you start out with a list of number from 2 to whatever (253 in your case)
You mark all these numbers as prime (think an array of booleans).
foreach number between 2 and 253 you go through the array looking for indices that are multiples of this number. Mark them as not prime.
You should be left with a list of all the primes up until 253.

There are optimisations you can make, such as not bothering to check even numbers.

At least if memory serves that's correct.

Trojan

This is a question of not doing someones homework methinks.

It doesn't really matter what language this is in, what you need to do is think about what defines a prime number and how to decide whether one is a prime or not.

A positive integer not divisible without a remainder by any positive integer other than itself and one.

So you need is a loop, for every number between 1 and 253, which checks each number to see if it's prime.

Now you need to decide how to check each number. One way of doing it is to divide it by every positive integer smaller than itself down to 1, and test the result to see if there's a remainder. "mod" is a good thing to think about here. Also remember this loop is a "step down" loop to use VB parlance.

That's enough info for the moment, don't go looking for more help until you've posted some pseudocode or some real code.

gl,
Al.

Trojan

Originally posted by Enygma
[stuff]

Nice to show different approaches
Admittedly yours is much more efficient.

Originally posted by Enygma
There are optimisations you can make, such as not bothering to check even numbers.

I remember when I was learning TCL about 4 years ago, having to write this program as part of the course.

My boss got really uptight about me insisting that we check 1, 2 and all the even numbers. I thought his implementation was incomplete without those checks

Al.

bonkey

Originally posted by Trojan

Nice to show different approaches
Admittedly yours is much more efficient.

A (possibly) more efficient way, which can be used to an open-ended target, is to check if your current number is divisible, but *only* by the primes you have found so far.

As a hint, the best way to do this is with a counter generating the test number, populating a (dynamic) array of primes as you find them.

Now - you have three ways to skin the same cat....for extra kudos, map the relative efficiency of all approaches

jc

Baz_

or an even more efficient way is to see if the number is divisible by all the primes you found up to and including the square root of the number youre checking the primeness of.

Don't ask me how it works, got it from a book but it works well.

Enygma

That's fine for testing to see if a number is prime but it doesn't give you all the prime numbers up until that number.
For example if you're checking 25 you check if it's divisible by 2, 3 and 5.
It's divisible by 5 so it's not prime.
But what about 7, 11, 13 etc. They're all primes.

It's a good algorithm for an isPrime() method but its not very efficient if you're looking for all the primes up until a certain number

bonkey

Originally posted by Enygma
That's fine for testing to see if a number is prime but it doesn't give you all the prime numbers up until that number.
For example if you're checking 25 you check if it's divisible by 2, 3 and 5.
It's divisible by 5 so it's not prime.
But what about 7, 11, 13 etc. They're all primes.

You're missing something...

To get to check 25, you have tested all numbers before 25. Therefore, you checked 7, and found that it was not divisible by 2, 3 or 5 (the primes found so far) and therefore deduced that it was prime.

It's a good algorithm for an isPrime() method but its not very efficient if you're looking for all the primes up until a certain number

There is no "good" algorithm for testing the "primeness" of a number, as it is essentiually the same problem as factoring - the difficulty of which is central to almost all mainstream key-pair encryption schemes.

Having though about the relative efficiencies over lunch, I would like to apologise to Enygma and say that his approach is far more efficient than my proposal, despite my initial thoughts

jc

Trojan

Jaysus you're gonna scare the poor guy off!

Al.

Enygma

I was talking about Baz_s one, that only checks as far as the square root.

I would like to apologise to Enygma and say that his approach is far more efficient than my proposal

Hehe I didn't invent it or anything I was just taught it.

I think it can be combined with your method to contain a cache of primes but that's a bit too much thought than I have time for right now

Enygma

Thinking about that square root thingy,

Use the sieve but only check multiples of numbers up until the square root of the number you're checking.

Giblet

x,y:number
x=11
y=2
output 1,' ',2,' ',3,' ',5,' ',7,' '
repeat
if ((x%2)=0) or ((x%3)=0) or ((x%5)=0) or ((x%7)=0) then
x=x+2
else
output x,' '
x=x+2
endif
until x=255

thats works
but it wont compile coz it's too big (it gets changed into machine code)

bonkey

Originally posted by Giblet

if ((x%2)=0) or ((x%3)=0) or ((x%5)=0) or ((x%7)=0) then

thats works

It works as what? This code outputs anything which is not divisible by 2, 3, 5, or 7. How does this show primes?

jc

Giblet

yes it works because a number that cant be divied by any of these is a prime and as u can see 1,2,3,5,7 are already outputed by the program before hand so these are not counted as x starts from 11

bonkey

143 is not divisible by 2, 3, 5 or 7.
143 is less than 253
143 is not prime (its 11*13).

Also, your algorithm doesnt calculate all primes between 2 and 253. It calculates all primes between 2 and 253, assuming that the first 4 primes are given. In other words, it is not finding all primes...it is finding some primes, having been given others.

For your approach to work, you would have to hardcode all primes below 16, which strikes me as a non-solution. In other words, you are solving :

Given that 2, 3, 5, 7, 11 and 13 are all the primes below 16, find all other primes less than the square of 16.

What you are not solving is :

Find all primes less than 253.

jc

p.s. I am not trying to dis you or detract from your efforts - I a trying to show why it is both incorrect and flawed.

Mixie

#include <stdio.h>
int prime_check(int);
void main(){
int x,y,prime_store[50],pc,count;
printf("Enter integer:");
scanf(" %d",&x);
count = 0;
for(y=1;y<=x;y++){
pc=prime_check(y);
if (pc==1){
prime_store[count]=y;
count++;
}
}
for (y=0;y<count;y++) printf("%d\n",prime_store[y]);
}
int prime_check(int p){
int x,flag,result;
flag=1;
for(x=2;x<p;x++){
if ((p%x)==0) flag=0;
}
return(flag);
}

Mixie

sorry about the lack of indentation, commenting etc. but the forum was saying the message was too long ( ? ).

Spunog UIE

CONNOLLY will ya do it yourself ya bum!!!!!!!

dumbasss

Hobbes

I pity the programmer who can't do his homework and is incapable of searching here or google.

Spunog UIE

yes truly a sad indivudal,
possibly a middle child starved of attention and so lacks the motivation to achieve!

SCAREY

EvilGeorge

Good, god man what are you going to do when you get a difficult program , research how to do it and do it your self , some help for research material maybe or you'll never make it.

GoneShootin

i thought giving out "free" code was not the done thing ?