-
Notifications
You must be signed in to change notification settings - Fork 0
/
051.asm
137 lines (117 loc) · 4.42 KB
/
051.asm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
format ELF64 executable 9
segment readable writable
result: times 10 db 0 ;empty string for printing the result later
db 10, 0
primes: times 125000 db 255 ;prime sieve (1e6 bits)
repd: rb 10 ;for counting repeated digits
segment readable executable
entry start
start:
mov ebx, 1 ;array index for outer loop
sieve_outer:
inc ebx ;increase index
mov eax, ebx ;copy to eax for squaring
mul ebx ;square
cmp eax, 1000000 ;check if square is > limit
jg reset ;if it is, jump to reset
bt [primes], ebx ;check if ebx is no prime
jnc sieve_outer ;if no prime, try next number
sieve_inner:
btr [primes], eax ;set multiple to not prime
add eax, ebx ;next multiple
cmp eax, 1000000 ;check if multiple is <= limit
jl sieve_inner ;if it is, continue with inner loop
jmp sieve_outer ;if not, continue with outer loop
reset:
mov edi, 1000 ;init index for primes
nextprime:
inc edi ;next number
bt [primes], edi ;is it prime?
jnc nextprime ;if not, try next
mov eax, edi ;prime in eax for divisions later
xor rsi, rsi ;reset rsi for clearing repd
mov [repd], rsi
mov [repd + 2], rsi
mov esi, 10 ;10 in esi for divisions
xor edx, edx ;reset remainder
div esi ;divide by 10 (drop last digit)
get_repd:
xor edx, edx ;reset remainder
div esi ;divide by 10
inc byte [repd + edx] ;increase digit count in repd[edx]
test eax, eax ;number reduced to 0?
jnz get_repd ;if not, repeat
xor esi, esi ;reset esi
get_012_count:
cmp esi, 3 ;0, 1 or 2 not repeated 3 times?
je nextprime ;then try next prime
mov al, [repd + esi] ;repd[esi] in al
cmp eax, 3 ;is count = 3?
je template ;if yes, make template
inc esi ;if not increase esi
jmp get_012_count ;and repeat
template:
mov eax, 10000000 ;tmp variable
mov ecx, 10 ;for divisions
getlength:
xor edx, edx ;reduce eax to length of edi
div ecx
cmp eax, edi
jg getlength
mov ebx, eax ;result in ebx
xor r8d, r8d ;will become the template
mov eax, edi ;number in eax
templateloop:
xor edx, edx ;reset remainder
div ebx ;divide by ebx
test edx, edx ;remainder = 0?
jz findfamily ;if yes, start finding the family
cmp eax, esi ;else compare current digit to repeated
mov eax, edx ;put remainder in eax
jne skipped ;if digit != repeated jump to skipped
add r8d, ebx ;else add ebx to template
skipped:
push rax ;reduce ebx and repeat
mov eax, ebx
xor edx, edx
div ecx
mov ebx, eax
pop rax
jmp templateloop
findfamily:
mov eax, edi ;prime in eax
mov ecx, esi
mov ebx, 1 ;counter for family size
familyloop:
cmp ebx, 8 ;family count = 8?
je finished ;if yes, we are finished
inc ecx
cmp ecx, 10 ;last possible replacement done?
je nextprime ;if yes, try next prime
add eax, r8d ;add template
bt [primes], eax ;is new number prime?
jnc familyloop ;if not, repeat
inc ebx ;else increase counter
jmp familyloop ;and try next substitution
finished:
mov eax, edi ;convert result to string, print and exit
mov ebx, 10
mov ecx, 9
convert_result:
xor edx, edx
div ebx
add edx, '0'
mov [result + ecx], dl
dec ecx
test eax, eax
jnz convert_result
print:
mov eax, 4
mov edi, 1
mov esi, result
mov edx, 12
syscall
exit:
mov rax, 1
xor rdi, rdi
syscall