prime numbers

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

  • : 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
    :

    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.
  • : : 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
    : :
    :
    : 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
  • : : : 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
    : : :
    : :
    : : 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.
  • [b][red]This message was edited by indicatoto101 at 2004-11-11 15:13:37[/red][/b][hr]
    : 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]






Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories