Hi guys I'm supposed to write a program that will display all prime numbers up to n(the number entered by the user). I'm unsure of what to do, should I use Sieve of ...(name escapes me). What is the best way to find if a number is prime? thanks for any help in advance
Comments
:
for a homework with a lower number of primes(just a few hunderts or less) its not that important what way you go.even trying to divide by all lower numbers to check for a prime is still fast enough on todays cpus.'TheSieveOf Whatever' needs a lot of memory ((N-1)*SizeOfNumber bytes for N numbers to check).
so in pseudo-code:
for(int i = 3;i < N;i++)
if( X/i == X mod I)
X is not Prime
else continue;
you can speed things a little up by checking only odd numbers.just start with 3 and add 2.even numbers never can be a prime.another way is to store all primes you already had found and just divide by them.another optimization is to divide only by numbers x<SQRT(N) when checking wether N is a prime or not.
when having to find large numbers of primes you may want to write your code for win32-assembly or under protected mode.finding ten-thousands of primes without any lookup-table(which must have at least the size to hold all the primes 3..N) takes longer times.however,for a homework you surely wont have to calculate lots of primes.
start with writing the loop from pseudo-code and ask questions to specific parts of it.
: :
:
: for a homework with a lower number of primes(just a few hunderts or less) its not that important what way you go.even trying to divide by all lower numbers to check for a prime is still fast enough on todays cpus.'TheSieveOf Whatever' needs a lot of memory ((N-1)*SizeOfNumber bytes for N numbers to check).
:
: so in pseudo-code:
: for(int i = 3;i < N;i++)
: if( X/i == X mod I)
: X is not Prime
: else continue;
:
: you can speed things a little up by checking only odd numbers.just start with 3 and add 2.even numbers never can be a prime.another way is to store all primes you already had found and just divide by them.another optimization is to divide only by numbers x<SQRT(N) when checking wether N is a prime or not.
:
: when having to find large numbers of primes you may want to write your code for win32-assembly or under protected mode.finding ten-thousands of primes without any lookup-table(which must have at least the size to hold all the primes 3..N) takes longer times.however,for a homework you surely wont have to calculate lots of primes.
:
: start with writing the loop from pseudo-code and ask questions to specific parts of it.
:
n can be up to 10,000 so theoretically there can be almost 5000 primes. Of course my instructor wants to display them ten at a time
: : :
: :
: : for a homework with a lower number of primes(just a few hunderts or less) its not that important what way you go.even trying to divide by all lower numbers to check for a prime is still fast enough on todays cpus.'TheSieveOf Whatever' needs a lot of memory ((N-1)*SizeOfNumber bytes for N numbers to check).
: :
: : so in pseudo-code:
: : for(int i = 3;i < N;i++)
: : if( X/i == X mod I)
: : X is not Prime
: : else continue;
: :
: : you can speed things a little up by checking only odd numbers.just start with 3 and add 2.even numbers never can be a prime.another way is to store all primes you already had found and just divide by them.another optimization is to divide only by numbers x<SQRT(N) when checking wether N is a prime or not.
: :
: : when having to find large numbers of primes you may want to write your code for win32-assembly or under protected mode.finding ten-thousands of primes without any lookup-table(which must have at least the size to hold all the primes 3..N) takes longer times.however,for a homework you surely wont have to calculate lots of primes.
: :
: : start with writing the loop from pseudo-code and ask questions to specific parts of it.
: :
:
:
:
:
: n can be up to 10,000 so theoretically there can be almost 5000 primes. Of course my instructor wants to display them ten at a time
:
ok,10000 arnt that much and displaying only 10 at a time will make hard speed-optimizations senseless.
so just make a loop which checks all numbers from N up to (N+10) wether its a prime or not.that could be easily done by divide the number by all numbers 3...N/SQRT(2) in a simple loop.
youve posted no specific code/problem so I assume you are on a good way.if not,just ask
good luck with your program.
: ok,10000 arnt that much and displaying only 10 at a time will make hard speed-optimizations senseless.
:
: so just make a loop which checks all numbers from N up to (N+10) wether its a prime or not.that could be easily done by divide the number by all numbers 3...N/SQRT(2) in a simple loop.
:
: youve posted no specific code/problem so I assume you are on a good way.if not,just ask
:
: good luck with your program.
:
Quite the contrary; I have no idea what to do next. Here is my code so far.
[code]
INCLUDE IRvine32.inc
.data
askuser BYTE "Enter a an integer b/t 1 & 10,000 inclusively", 0
telluser BYTE "number is not prime", 0
tellinputer BYTE "number is prime", 0
.code
main PROC
Laskuser:
mov edx, OFFSET askuser
call Writestring
call crlf
call Readint
cmp eax, 0
jle Laskuser
cmp eax, 10000
jg Laskuser ;jump to label again if number is less than 0
mov ecx, eax ;ecx = N(number entered by user)
mov ebx, 2 ;use 2 as divisor to
L1:
mov edx, 0
cmp eax, ebx
je prime ;jump if n and 2 are equal
push eax
div ebx ;divide n by 2
cmp edx, 0
je notprime ;if the remainder of n and 2 is 0, n is not prime
pop eax
inc ebx ;otherwise, increment 2 and test again
loop L1
prime:
mov ebx, eax
mov esi, 10
xor ecx, ecx
ret
notprime:
pop eax
mov edx, offset telluser
call WriteString
exit
main ENDP
END main
[/code]
: : ok,10000 arnt that much and displaying only 10 at a time will make hard speed-optimizations senseless.
: :
: : so just make a loop which checks all numbers from N up to (N+10) wether its a prime or not.that could be easily done by divide the number by all numbers 3...N/SQRT(2) in a simple loop.
: :
: : youve posted no specific code/problem so I assume you are on a good way.if not,just ask
: :
: : good luck with your program.
: :
:
:
:
: Quite the contrary; I have no idea what to do next. Here is my code so far.
:
: [code]
:
: INCLUDE IRvine32.inc
:
: .data
:
: askuser BYTE "Enter a an integer b/t 1 & 10,000 inclusively", 0
: telluser BYTE "number is not prime", 0
: tellinputer BYTE "number is prime", 0
:
: .code
: main PROC
:
:
: Laskuser:
:
: mov edx, OFFSET askuser
: call Writestring
: call crlf
: call Readint
:
: cmp eax, 0
: jle Laskuser
: cmp eax, 10000
: jg Laskuser ;jump to label again if number is less than 0
:
:
: mov ecx, eax ;ecx = N(number entered by user)
: mov ebx, 2 ;use 2 as divisor to
:
: L1:
: mov edx, 0
: cmp eax, ebx
: je prime ;jump if n and 2 are equal
:
: push eax
: div ebx ;divide n by 2
:
:
: cmp edx, 0
: je notprime ;if the remainder of n and 2 is 0, n is not prime
:
: pop eax
: inc ebx ;otherwise, increment 2 and test again
: loop L1
:
:
: prime:
: mov ebx, eax
: mov esi, 10
: xor ecx, ecx
: ret
: notprime:
: pop eax
: mov edx, offset telluser
: call WriteString
:
:
:
:
: exit
: main ENDP
: END main
ok,i just read over your code but it looks fine.have you tested it,does it work for all entered numbers you tried?now that you have a working prime-check its time to put it in a subroutine which checks it for prime:
IsPrime PROC
;... check e.g. EAX for prime
IsPrime:
mov eax,1
ret
IsNotPrime:
mov eax,0
ret
IsPrime ENDP
now create a loop in your main-code which runs through all numbers from 2 (or 3 or 4,whereever you need to start) and calls your subroutine.afterwards check eax for 1 or 0 and outputs the currently checked number when its a 1.maybe you can add a counter-variable which controls a user-prompt evry 10 outputed primes.
you included a file for string-output/input (irvine32.inc).i never used that library,but it surley contains functions to convert numbers to strings and display that.
L2:
mov eax,ecx
call IsPrime
cmp eax,0
je NotPrime
; convert number in ecx to string and output it
; increase counter and wait for keypress if it reaches 10
; if Counter == 10 -> reset counter
NotPrime:
inc ecx
cmp ecx,[N]
jne L2
ok,i hope this will help you to create your code.when you have a working copy post it here.I will send you a copy of my Prime-code when youre done.it does not output anything,but creates a file with primes when it exits.my code is optimized for speed and not good for learning the basics,but i think you might be interested.
: ok,i just read over your code but it looks fine.have you tested it,does it work for all entered numbers you tried?now that you have a working prime-check its time to put it in a subroutine which checks it for prime:
:
: IsPrime PROC
: ;... check e.g. EAX for prime
: IsPrime:
: mov eax,1
: ret
: IsNotPrime:
: mov eax,0
: ret
: IsPrime ENDP
:
: now create a loop in your main-code which runs through all numbers from 2 (or 3 or 4,whereever you need to start) and calls your subroutine.afterwards check eax for 1 or 0 and outputs the currently checked number when its a 1.maybe you can add a counter-variable which controls a user-prompt evry 10 outputed primes.
:
: you included a file for string-output/input (irvine32.inc).i never used that library,but it surley contains functions to convert numbers to strings and display that.
:
: L2:
: mov eax,ecx
: call IsPrime
: cmp eax,0
: je NotPrime
:
: ; convert number in ecx to string and output it
: ; increase counter and wait for keypress if it reaches 10
: ; if Counter == 10 -> reset counter
:
: NotPrime:
: inc ecx
: cmp ecx,[N]
: jne L2
:
: ok,i hope this will help you to create your code.when you have a working copy post it here.I will send you a copy of my Prime-code when youre done.it does not output anything,but creates a file with primes when it exits.my code is optimized for speed and not good for learning the basics,but i think you might be interested.
:
I don't know.... I am doing it a little differently. I'm just incrementing eax from one to whatever until it reaches and it displays the prime numbers in the process. Doesen't seem to work, of course it's much more challenging than this! Here is the code so far. For some reason it only displays one.
[code]
INCLUDE IRvine32.inc
.data
askuser BYTE "Enter a an integer b/t 1 & 10,000 inclusively", 0dh, 0ah
BYTE "and I will display the primes less than it",0dh, 0ah
BYTE "given the above conditions",0
telluser BYTE "number is not prime", 0
tellinputer BYTE "number is prime", 0
oneis BYTE " 1 is prime", 0
max_number DWORD ?
.code
main PROC
Laskuser:
mov edx, OFFSET askuser
call Writestring
call crlf
call Readint
cmp eax, 0
jle Laskuser
cmp eax, 10000
jg Laskuser ;jump to label again if number is less than 0
mov max_number, eax
mov eax, 1
jmp isprime
next:
inc eax
mov ebx, 1
mov ecx, max_number ;ecx = N(number entered by user)
;use 2 as divisor to L1:
Begintest:
inc ebx
mov edx, 0
cmp eax, ebx
je isprime ;jump if n and 2 are equal
push eax
div ebx ;divide n by 2
cmp edx, 0
jne isprime ;if the remainder of n and 2 is 0, n is not prime
;add ebx, 2
pop eax
jne next ;otherwise, increment 2 and test again
loop Begintest
isprime:
call writeint
ret
notprime:
;pop eax
mov edx, offset telluser
call WriteString
exit
main ENDP
END main
[/code]